The Library
Zigzagging through acyclic orientations of graphs and hypergraphs
Tools
Cardinal, Jean, Hoang, Hung, Merino, Arturo, Micka, Ondrej and Mutze, Torsten (2023) Zigzagging through acyclic orientations of graphs and hypergraphs. In: 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Florence, Italy, 22-25 Jan 2023. Published in: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) pp. 3029-3042. ISBN 9781611977554. doi:10.1137/1.9781611977554.ch117
|
PDF
WRAP-Zigzagging-through-acyclic-orientations-chordal-graphs-hypergraphs-22.pdf - Accepted Version - Requires a PDF viewer. Download (1130Kb) | Preview |
Official URL: https://doi.org/10.1137/1.9781611977554.ch117
Abstract
In 1993, Savage, Squire, and West described an inductive construction for generating every acyclic orientation of a chordal graph exactly once, flipping one arc at a time.
We provide two generalizations of this result.
Firstly, we describe Gray codes for acyclic orientations of hypergraphs that satisfy a simple ordering condition, which generalizes the notion of perfect elimination order of graphs.
This unifies the Savage-Squire-West construction with a recent algorithm for generating elimination trees of chordal graphs (SODA~2022).
Secondly, we consider quotients of lattices of acyclic orientations of chordal graphs, and we provide a Gray code for them, addressing a question raised by Pilaud (FPSAC~2022).
This also generalizes a recent algorithm for generating lattice congruences of the weak order on the symmetric group (SODA~2020).
Our algorithms are derived from the Hartung-Hoang-M\"utze-Williams combinatorial generation framework, and they yield simple algorithms for computing Hamilton paths and cycles on large classes of polytopes, including chordal nestohedra and quotientopes.
In particular, we derive an efficient implementation of the Savage-Squire-West construction.
Along the way, we give an overview of old and recent results about the polyhedral and order-theoretic aspects of acyclic orientations of graphs and hypergraphs.
Item Type: | Conference Item (Paper) | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||
Library of Congress Subject Headings (LCSH): | Gray codes, Computer algorithms, Graph algorithms, Hypergraphs , Graph theory | ||||||||||||
Journal or Publication Title: | Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) | ||||||||||||
Publisher: | Society for Industrial and Applied Mathematics | ||||||||||||
ISBN: | 9781611977554 | ||||||||||||
Official Date: | 16 January 2023 | ||||||||||||
Dates: |
|
||||||||||||
Page Range: | pp. 3029-3042 | ||||||||||||
DOI: | 10.1137/1.9781611977554.ch117 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Access rights to Published version: | Free Access (unspecified licence, 'bronze OA') | ||||||||||||
Copyright Holders: | Copyright © 2023 by SIAM | ||||||||||||
Date of first compliant deposit: | 8 December 2022 | ||||||||||||
Date of first compliant Open Access: | 13 March 2023 | ||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||
Conference Paper Type: | Paper | ||||||||||||
Title of Event: | 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023) | ||||||||||||
Type of Event: | Conference | ||||||||||||
Location of Event: | Florence, Italy | ||||||||||||
Date(s) of Event: | 22-25 Jan 2023 | ||||||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year