Self-adjusting top trees

Robert E. Tarjan, Renato F. Werneck

Research output: Contribution to conferencePaperpeer-review

38 Scopus citations

Abstract

The dynamic trees problem is that of maintaining a forest that changes over time through edge insertions and deletions. We can associate data with vertices or edges, and manipulate this data individually or in bulk, with operations that deal with whole paths or trees. Efficient solutions to this problem have numerous applications, particularly in algorithms for network flows and dynamic graphs in general. Several data structures capable of logarithmic-time dynamic tree operations have been proposed. The first was Sleator and Tarjan's ST-tree [16, 17], which represents a partition of the tree into paths. Although reasonably fast in practice, adapting ST-trees to different applications is nontrivial. Topology trees [9], top trees [3], and RC-trees [1] are based on tree contractions: they progressively combine vertices or edges to obtain a hierarchical representation of the tree. This approach is more flexible in theory, but all known implementations assume the trees have bounded degree; arbitrary trees are supported only after ternarization. We show how these two approaches can be combined (with very little overhead) to produce a data structure that is as generic as any other, very easy to adapt, and as practical as ST-trees.

Original languageEnglish (US)
Pages813-822
Number of pages10
StatePublished - 2005
EventSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States
Duration: Jan 23 2005Jan 25 2005

Other

OtherSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityVancouver, BC
Period1/23/051/25/05

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Self-adjusting top trees'. Together they form a unique fingerprint.

Cite this