Skip to main content

Disjoint Set Union with Randomized Linking

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

To refer to this page use:
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 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.
Publication Date: 2014
Citation: Goel, 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.75
DOI: 10.1137/1.9781611973402.75
Pages: 1005 - 1017
Type of Material: Conference Article
Journal/Proceeding Title: ACM-SIAM Symposium on Discrete Algorithms
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.