Splay Top Trees

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Documents

  • Fulltext

    Final published version, 407 KB, PDF document

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.
Original languageEnglish
Title of host publicationSymposium on Simplicity in Algorithms (SOSA)
EditorsTelikepalli Kavitha, Kurt Mehlhorn
PublisherSociety for Industrial and Applied Mathematics
Publication date2023
Pages305-331
ISBN (Electronic)978-1-61197-758-5
DOIs
Publication statusPublished - 2023
Event2023 Symposium on Simplicity in Algorithms (SOSA) - Florence, Italy
Duration: 23 Jan 202325 Jan 2023

Conference

Conference2023 Symposium on Simplicity in Algorithms (SOSA)
LandItaly
ByFlorence
Periode23/01/202325/01/2023

ID: 383441844