Disjoint set union with randomized linking

Ashish Goel, Sanjeev Khanna, Daniel H. Larkin, Robert E. Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
PublisherAssociation for Computing Machinery
Pages1005-1017
Number of pages13
ISBN (Print)9781611973389
DOIs
StatePublished - Jan 1 2014
Event25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 - Portland, OR, United States
Duration: Jan 5 2014Jan 7 2014

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
CountryUnited States
CityPortland, OR
Period1/5/141/7/14

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Disjoint set union with randomized linking'. Together they form a unique fingerprint.

Cite this