# Disjoint Set Union with Randomized Linking

## Author(s): Goel, Ashish; Khanna, Sanjeev; Larkin, Daniel H; Tarjan, Robert E

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1zc1z
DC FieldValueLanguage
dc.contributor.authorGoel, Ashish-
dc.contributor.authorKhanna, Sanjeev-
dc.contributor.authorLarkin, Daniel H-
dc.contributor.authorTarjan, Robert E-
dc.date.accessioned2021-10-08T19:47:30Z-
dc.date.available2021-10-08T19:47:30Z-
dc.date.issued2014en_US
dc.identifier.citationGoel, Ashish, Sanjeev Khanna, Daniel H. Larkin, and Robert E. Tarjan. "Disjoint Set Union with Randomized Linking." In ACM-SIAM Symposium on Discrete Algorithms (2014): pp. 1005-1017. doi:10.1137/1.9781611973402.75en_US
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1zc1z-
dc.description.abstractA 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 naïve 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.en_US
dc.format.extent1005 - 1017en_US
dc.language.isoen_USen_US
dc.relation.ispartofACM-SIAM Symposium on Discrete Algorithmsen_US
dc.rightsAuthor's manuscripten_US
dc.titleDisjoint Set Union with Randomized Linkingen_US
dc.typeConference Articleen_US
dc.identifier.doi10.1137/1.9781611973402.75-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat