License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2022.14
URN: urn:nbn:de:0030-drops-161743
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16174/
Berendsohn, Benjamin Aram
The Diameter of Caterpillar Associahedra
Abstract
The caterpillar associahedron ?(G) is a polytope arising from the rotation graph of search trees on a caterpillar tree G, generalizing the rotation graph of binary search trees (BSTs) and thus the conventional associahedron. We show that the diameter of ?(G) is Θ(n + m ⋅ (H+1)), where n is the number of vertices, m is the number of leaves, and H is the entropy of the leaf distribution of G.
Our proofs reveal a strong connection between caterpillar associahedra and searching in BSTs. We prove the lower bound using Wilber’s first lower bound for dynamic BSTs, and the upper bound by reducing the problem to searching in static BSTs.
BibTeX - Entry
@InProceedings{berendsohn:LIPIcs.SWAT.2022.14,
author = {Berendsohn, Benjamin Aram},
title = {{The Diameter of Caterpillar Associahedra}},
booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
pages = {14:1--14:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-236-5},
ISSN = {1868-8969},
year = {2022},
volume = {227},
editor = {Czumaj, Artur and Xin, Qin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16174},
URN = {urn:nbn:de:0030-drops-161743},
doi = {10.4230/LIPIcs.SWAT.2022.14},
annote = {Keywords: Graph Associahedra, Binary Search Trees, Elimination Trees}
}
|
Keywords: |
|
Graph Associahedra, Binary Search Trees, Elimination Trees |
|
Collection: |
|
18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
22.06.2022 |
