TY - GEN
T1 - Disjoint set union with randomized linking
AU - Goel, Ashish
AU - Khanna, Sanjeev
AU - Larkin, Daniel H.
AU - Tarjan, Robert E.
N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2014
Y1 - 2014
N2 - A classic result in the analysis of data structures is that path compression with linking by rank solves the disjoint set union problem in almost-constant amortized time per operation. Recent experiments suggest that in practice, a naive linking method works just as well if not better than linking by rank, in spite of being theoretically inferior. How can this be? We prove that randomized linking is asymptotically as efficient as linking by rank. This result provides theory that matches the experiments, which implicitly do randomized linking as a result of the way the input instances are generated.
AB - A classic result in the analysis of data structures is that path compression with linking by rank solves the disjoint set union problem in almost-constant amortized time per operation. Recent experiments suggest that in practice, a naive linking method works just as well if not better than linking by rank, in spite of being theoretically inferior. How can this be? We prove that randomized linking is asymptotically as efficient as linking by rank. This result provides theory that matches the experiments, which implicitly do randomized linking as a result of the way the input instances are generated.
UR - http://www.scopus.com/inward/record.url?scp=84902097285&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84902097285&partnerID=8YFLogxK
U2 - 10.1137/1.9781611973402.75
DO - 10.1137/1.9781611973402.75
M3 - Conference contribution
AN - SCOPUS:84902097285
SN - 9781611973389
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 1005
EP - 1017
BT - Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
PB - Association for Computing Machinery
T2 - 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
Y2 - 5 January 2014 through 7 January 2014
ER -