TY - GEN

T1 - Disjoint set union with randomized linking

AU - Goel, Ashish

AU - Khanna, Sanjeev

AU - Larkin, Daniel H.

AU - Tarjan, Robert E.

PY - 2014/1/1

Y1 - 2014/1/1

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 -