The Library
Efficient generation of elimination trees and graph associahedra
Tools
Tools
Tools
Cardinal, Jean, Merino, Arturo and Mutze, Torsten (2022) Efficient generation of elimination trees and graph associahedra. In: 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), Virtual Conference, 09-12 Jan 2022. Published in: Proceedings of SODA 2022 pp. 2128-2140. ISBN 9781611977073. doi:10.1137/1.9781611977073.84
|
PDF
WRAP-Efficient-generation-elimination-trees-graph-associahedra-2022.pdf - Accepted Version - Requires a PDF viewer. Download (1904Kb) | Preview |
Official URL: http://doi.org/10.1137/1.9781611977073.84
Abstract
An elimination tree for a connected graph~$G$ is a rooted tree on the vertices of~$G$ obtained by choosing a root~$x$ and recursing on the connected components of~$G-x$ to produce the subtrees of~$x$.
Elimination trees appear in many guises in computer science and discrete mathematics, and they encode many interesting combinatorial objects, such as bitstrings, permutations and binary trees.
We apply the recent Hartung-Hoang-M\"utze-Williams combinatorial generation framework to elimination trees, and prove that all elimination trees for a chordal graph~$G$ can be generated by tree rotations using a simple greedy algorithm.
This yields a short proof for the existence of Hamilton paths on graph associahedra of chordal graphs.
Graph associahedra are a general class of high-dimensional polytopes introduced by Carr, Devadoss, and Postnikov, whose vertices correspond to elimination trees and whose edges correspond to tree rotations.
As special cases of our results, we recover several classical Gray codes for bitstrings, permutations and binary trees, and we obtain a new Gray code for partial permutations.
Our algorithm for generating all elimination trees for a chordal graph~$G$ can be implemented in time~$\cO(m+n)$ per generated elimination tree, where $m$ and~$n$ are the number of edges and vertices of~$G$, respectively.
If $G$ is a tree, we improve this to a loopless algorithm running in time~$\cO(1)$ per generated elimination tree.
We also prove that our algorithm produces a Hamilton cycle on the graph associahedron of~$G$, rather than just Hamilton path, if the graph~$G$ is chordal and 2-connected.
Moreover, our algorithm characterizes chordality, i.e., it computes a Hamilton path on the graph associahedron of~$G$ if and only if $G$ is chordal.
| Item Type: | Conference Item (Paper) | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics 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): | Combinatorial analysis , Discrete mathematics, Computer algorithms, Permutations , Binary system (Mathematics), Gray codes, Graph algorithms | ||||||||||||
| Journal or Publication Title: | Proceedings of SODA 2022 | ||||||||||||
| Publisher: | SIAM | ||||||||||||
| ISBN: | 9781611977073 | ||||||||||||
| Official Date: | 5 January 2022 | ||||||||||||
| Dates: |
|
||||||||||||
| Page Range: | pp. 2128-2140 | ||||||||||||
| DOI: | 10.1137/1.9781611977073.84 | ||||||||||||
| Status: | Peer Reviewed | ||||||||||||
| Publication Status: | Published | ||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||||||
| RIOXX Funder/Project Grant: |
|
||||||||||||
| Conference Paper Type: | Paper | ||||||||||||
| Title of Event: | 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022) | ||||||||||||
| Type of Event: | Conference | ||||||||||||
| Location of Event: | Virtual Conference | ||||||||||||
| Date(s) of Event: | 09-12 Jan 2022 | ||||||||||||
| Related URLs: | |||||||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
