Efficient generation of elimination trees and graph associahedra

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10450766" target="_blank" >RIV/00216208:11320/22:10450766 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1137/1.9781611977073.84" target="_blank" >https://doi.org/10.1137/1.9781611977073.84</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/1.9781611977073.84" target="_blank" >10.1137/1.9781611977073.84</a>

Result language

angličtina

Original language name

Efficient generation of elimination trees and graph associahedra

Original language description

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ütze-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 O(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 O(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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA19-08554S" target="_blank" >GA19-08554S: Structures and algorithms in highly symmetric graphs</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2022

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)

ISBN

978-1-61197-707-3

ISSN

—

e-ISSN

—

Number of pages

13

Pages from-to

2128-2140

Publisher name

Society for Industrial and Applied Mathematics

Place of publication

Philadelphia, USA

Event location

Alexandria, Virgina, U.S.; Virtual

Event date

Jan 9, 2022

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—