Complexity of algorithm and operations on trees

DOI10.1016/0304-3975(93)90312-HMaRDI QIDQ688696zbMATH OpenOpenAlexFDO

Authors Serge Dulucq, Sophie Gire

Publication date 12 December 1993

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(93)90312-h

zbMATH Keywords

mutual exclusion algorithmoperations on treespath compressionpaths reversal

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Review text

We consider operations on trees like paths reversal and standard path compression. These operations are used in the algorithm to maintain disjoint sets under union [\textit{R. E. Tarjan} and \textit{J. van Leeuwen}, J. Assoc. Comput. Mech. 31, 245-281 (1984; Zbl 0632.68043)]. The path reversal had been used in a recent mutual exclusion algorithm [\textit{M. Trehel} and \textit{M. M. Naimi}, Tech. Sci. Inf. 6, 141-150 (1987; Zbl 0618.68037)]. We give exact values for the worst-case of a sequence of these operations performed on an arbitrary initial tree. To obtain these results, we first give upper bounds by applying the potential function method of amortized analysis introduced by \textit{R. E. Tarjan} [SIAM J. Algebraic Discrete Methods 6, 306-318 (1985; Zbl 0599.68046)]. Then, we show up sequences of operations which costs are exactly the upper proved bounds.

Recommendations

• A tight amortized bound for path reversal
• On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem
• scientific article; zbMATH DE number 3907792
• Top-Down Analysis of Path Compression
• Worst-case Analysis of Set Union Algorithms

Cites work

• A tight amortized bound for path reversal
• Amortized Computational Complexity
• An improved equivalence algorithm
• Complexity of algorithm and operations on trees
• Efficiency of Equivalence Algorithms
• Finding Minimum Spanning Trees
• scientific article; zbMATH DE number 4003522 (Why is no real title available?)
• On the computational power of pushdown automata
• Self-adjusting binary search trees
• Worst-case Analysis of Set Union Algorithms

Cited in

(10)

• An asymptotic study for path reversal.
• The recognition of union trees
• On the Expected Performance of Path Compression Algorithms
• scientific article; zbMATH DE number 2044508 (Why is no real title available?)
• scientific article; zbMATH DE number 844505 (Why is no real title available?)
• Top-Down Analysis of Path Compression
• Transactions on Rough Sets III
• Complexity analysis of tree share structure
• Complexity of algorithm and operations on trees
• On the complexity of computing treelength

This page was built for publication: Complexity of algorithm and operations on trees

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