On the Expected Performance of Path Compression Algorithms

DOI10.1137/0214010zbMath0563.68043OpenAlexW2147247482MaRDI QIDQ3677175

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)

Related Items

Components of Random Forests, Perfect hashing, An optimal algorithm for generating minimal perfect hash functions, Normal convergence problem? Two moments and a recurrence may be the clues