Top-Down Analysis of Path Compression

DOI10.1137/S0097539703439088MaRDI QIDQ5317162zbMATH OpenFDO

Authors Raimund Seidel, Micha Sharir

Publication date 16 September 2005

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539703439088

zbMATH Keywords

disjoint sets data structureinverse Ackermann functionpath compressionunion-find problem

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms (68W40)

Recommendations

• Worst-case Analysis of Set Union Algorithms
• Union-find with constant time deletions
• Complexity of algorithm and operations on trees
• scientific article; zbMATH DE number 6297801
• Worst-case and amortised optimality in union-find (extended abstract)

Cited in

(6)

• Semi-dynamic connectivity in the plane
• On the Expected Performance of Path Compression Algorithms
• Worst-case Analysis of Set Union Algorithms
• The Inverse of Ackermann Function is Computable in Linear Time
• Verifying the correctness and amortized complexity of a union-find implementation in separation logic with time credits
• Complexity of algorithm and operations on trees

This page was built for publication: Top-Down Analysis of Path Compression

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