Design of data structures for mergeable trees

Loukas Georgiadis, Robert Endre Tarjan, Renato F. Werneck

Research output: Contribution to conferencePaper

9 Scopus citations

Abstract

Motivated by an application in computational topology, we consider a novel variant of the problem of efficiently maintaining dynamic rooted trees. This variant allows an operation that merges two tree paths. In contrast to the standard problem, in which only one tree arc at a time changes, a single merge operation can change many arcs. In spite of this, we develop a data structure that supports merges and all other standard tree operations in O(log 2 n) amortized time on an n-node forest. For the special case that occurs in the motivating application, in which arbitrary arc deletions are not allowed, we give a data structure with an O(log n) amortized time bound per operation, which is asymptotically optimal. The analysis of both algorithms is not straightforward and requires ideas not previously used in the study of dynamic trees. We explore the design space of algorithms for the problem and also consider lower bounds for it.

Original languageEnglish (US)
Pages394-403
Number of pages10
DOIs
StatePublished - Feb 28 2006
EventSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms - Miami, FL, United States
Duration: Jan 22 2006Jan 24 2006

Other

OtherSeventeenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityMiami, FL
Period1/22/061/24/06

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Design of data structures for mergeable trees'. Together they form a unique fingerprint.

  • Cite this

    Georgiadis, L., Tarjan, R. E., & Werneck, R. F. (2006). Design of data structures for mergeable trees. 394-403. Paper presented at Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, United States. https://doi.org/10.1145/1109557.1109602