On the Expected Performance of Path Compression Algorithms

DOI10.1137/0214010MaRDI QIDQ3677175zbMATH OpenOpenAlexFDO

Authors Andrew Chi-Chih Yao

Publication date 1985

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

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

zbMATH Keywords

expected running timepath compressionmean behaviorequivalence programset mergingspanning tree model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Probabilistic Analysis of Disjoint Set Union Algorithms
• Complexity of algorithm and operations on trees
• Worst-case Analysis of Set Union Algorithms
• Top-Down Analysis of Path Compression
• Analysis of the total costs for variants of the union-find algorithm

Cited in

(6)

• Fast Compressed Tries through Path Decompositions
• Components of Random Forests
• Normal convergence problem? Two moments and a recurrence may be the clues
• An optimal algorithm for generating minimal perfect hash functions
• Fast compressed tries through path decompositions
• Perfect hashing

This page was built for publication: On the Expected Performance of Path Compression Algorithms

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