Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

[img]
Preview
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

Request Changes to record.

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:
DateEvent
5 January 2022Available
2 October 2021Accepted
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:
Project/Grant IDRIOXX Funder NameFunder ID
2019-72200522ANID Becas Chilehttps://www.anid.cl/
GA 19-08554SGrantová Agentura České Republikyhttp://dx.doi.org/10.13039/501100001824
413902284[DFG] Deutsche Forschungsgemeinschafthttp://dx.doi.org/10.13039/501100001659
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:
  • Organisation
  • Open Access File
Open Access Version:
  • ArXiv

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us