Data structures for mergeable trees

DOI10.1145/1921659.1921660MaRDI QIDQ3188996zbMATH OpenOpenAlexFDO

Authors Loukas Georgiadis, Haim Kaplan, Nira Shafrir, Renato F. Werneck, Robert E. Tarjan

Publication date 9 September 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0711.1682

zbMATH Keywords

amortized efficiencycomputational topologycritical pairsdynamic treesextreme pointslink-cut treesmanifoldsmerging

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Motivated by an application in computational topology, we consider a novel variant of the problem of efficiently maintaining dynamic rooted trees. This variant requires merging two paths in a single operation. In contrast to the standard problem, in which only one tree arc changes at a time, a single merge operation can change many arcs. In spite of this, we develop a data structure that supports merges on an n-node forest in O(log^2 n) amortized time and all other standard tree operations in O(log n) time (amortized, worst-case, or randomized depending on the underlying data structure). For the special case that occurs in the motivating application, in which arbitrary arc deletions (cuts) are not allowed, we give a data structure with an O(log n) time bound per operation. This is asymptotically optimal under certain assumptions. For the even-more special case in which both cuts and parent queries are disallowed, we give an alternative O(log n)-time solution that uses standard dynamic trees as a black box. This solution also applies to the motivating application. Our methods use previous work on dynamic trees in various ways, but the analysis of each algorithm requires novel ideas. We also investigate lower bounds for the problem under various assumptions.

Recommendations

• Algorithmic Aspects of Tree Amalgamation
• Triplet merge trees
• Decorated merge trees for persistent topology
• A Data Structure for Dynamically Maintaining Rooted Trees
• scientific article; zbMATH DE number 437542
• scientific article; zbMATH DE number 140488
• A tree-based mergesort
• Combining binary search trees
• scientific article; zbMATH DE number 3949727
• scientific article; zbMATH DE number 934534

Cited in

(20)

• On the dynamization of data structures
• A tree-based mergesort
• Merge trees in discrete Morse theory
• Blame trees
• Union-copy structures and dynamic segment trees
• Versioning Tree Structures by Path-Merging
• Path Minima in Incremental Unrooted Trees
• Mergeable dictionaries
• A correction to Andersson's fusion tree construction
• scientific article; zbMATH DE number 140488 (Why is no real title available?)
• Efficient splitting and merging algorithms for order decomposable problems
• scientific article; zbMATH DE number 827974 (Why is no real title available?)
• Concatenable segment trees (extended abstract)
• Batch-parallel Euler tour trees
• A simple mergeable dictionary
• Amortized Rigidness in Dynamic Cartesian Trees
• Revisiting graph persistence for updates and efficiency
• Enhancing graph representation learning with localized topological features
• Computing zigzag persistence on graphs in near-linear time
• Computing Betti tables and minimal presentations of zero-dimensional persistent homology

This page was built for publication: Data structures for mergeable trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3188996)