Splay Top Trees
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Splay Top Trees. / Holm, Jacob; Rotenberg, Eva; Ryhl, Alice.
Symposium on Simplicity in Algorithms (SOSA). ed. / Telikepalli Kavitha; Kurt Mehlhorn. Society for Industrial and Applied Mathematics, 2023. p. 305-331.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Splay Top Trees
AU - Holm, Jacob
AU - Rotenberg, Eva
AU - Ryhl, Alice
PY - 2023
Y1 - 2023
N2 - The top tree data structure is an important and fundamental tool in dynamic graph algorithms. Top trees have existed for decades, and today serve as an ingredient in many state-of-the-art algorithms for dynamic graphs. In this work, we give a new direct proof of the existence of top trees, facilitating simpler and more direct implementations of top trees, based on ideas from splay trees. This result hinges on new insights into the structure of top trees, and in particular the structure of each root path in a top tree. In amortized analysis, our top trees match the asymptotic bounds of the state of the art.
AB - The top tree data structure is an important and fundamental tool in dynamic graph algorithms. Top trees have existed for decades, and today serve as an ingredient in many state-of-the-art algorithms for dynamic graphs. In this work, we give a new direct proof of the existence of top trees, facilitating simpler and more direct implementations of top trees, based on ideas from splay trees. This result hinges on new insights into the structure of top trees, and in particular the structure of each root path in a top tree. In amortized analysis, our top trees match the asymptotic bounds of the state of the art.
U2 - 10.1137/1.9781611977585.ch28
DO - 10.1137/1.9781611977585.ch28
M3 - Article in proceedings
SP - 305
EP - 331
BT - Symposium on Simplicity in Algorithms (SOSA)
A2 - Kavitha, Telikepalli
A2 - Mehlhorn, Kurt
PB - Society for Industrial and Applied Mathematics
T2 - 2023 Symposium on Simplicity in Algorithms (SOSA)
Y2 - 23 January 2023 through 25 January 2023
ER -
ID: 383441844