Dynamic trees in practice

Robert E. Tarjan, Renato F. Werneck

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

Dynamic tree data structures maintain forests that change over time through edge insertions and deletions. Besides maintaining connectivity information in logarithmic time, they can support aggregation of information over paths, trees, or both. We perform an experimental comparison of several versions of dynamic trees: ST-trees, ET-trees, RC-trees, and two variants of top trees (self-adjusting and worst-case). We quantify their strengths and weaknesses through tests with various workloads, most stemming from practical applications. We observe that a simple, linear-time implementation is remarkably fast for graphs of small diameter, and that worst-case and randomized data structures are best when queries are very frequent. The best overall performance, however, is achieved by self-adjusting ST-trees.

Original languageEnglish (US)
Title of host publicationExperimental Algorithms - 6th International Workshop, WEA 2007, Proceedings
PublisherSpringer Verlag
Pages80-93
Number of pages14
ISBN (Print)3540728449, 9783540728443
DOIs
StatePublished - 2007
Event6th International Workshop on Experimental Algorithms, WEA 2007 - Rome, Italy
Duration: Jun 6 2007Jun 8 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4525 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other6th International Workshop on Experimental Algorithms, WEA 2007
CountryItaly
CityRome
Period6/6/076/8/07

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Dynamic trees in practice'. Together they form a unique fingerprint.

  • Cite this

    Tarjan, R. E., & Werneck, R. F. (2007). Dynamic trees in practice. In Experimental Algorithms - 6th International Workshop, WEA 2007, Proceedings (pp. 80-93). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4525 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-72845-0_7