Splay Top Trees

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Dokumenter

  • Fulltext

    Forlagets udgivne version, 407 KB, PDF-dokument

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.
OriginalsprogEngelsk
TitelSymposium on Simplicity in Algorithms (SOSA)
RedaktørerTelikepalli Kavitha, Kurt Mehlhorn
ForlagSociety for Industrial and Applied Mathematics
Publikationsdato2023
Sider305-331
ISBN (Elektronisk)978-1-61197-758-5
DOI
StatusUdgivet - 2023
Begivenhed2023 Symposium on Simplicity in Algorithms (SOSA) - Florence, Italien
Varighed: 23 jan. 202325 jan. 2023

Konference

Konference2023 Symposium on Simplicity in Algorithms (SOSA)
LandItalien
ByFlorence
Periode23/01/202325/01/2023

ID: 383441844