Disjoint set union with randomized linking

DOI10.1137/1.9781611973402.75MaRDI QIDQ5384037zbMATH OpenOpenAlexFDO

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

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973402.75

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40) Data structures (68P05)

Recommendations

• Probabilistic Analysis of Disjoint Set Union Algorithms
• scientific article; zbMATH DE number 2119640
• A randomized concurrent algorithm for disjoint set union
• Concurrent disjoint set union
• Worst-case Analysis of Set Union Algorithms

Cited in

(5)

• Analysis of the total costs for variants of the union-find algorithm
• A linear-time algorithm for a special case of disjoint set union
• Random linkage: A family of acceptance/rejection algorithms for global sation
• Probabilistic Analysis of Disjoint Set Union Algorithms
• Concurrent disjoint set union

This page was built for publication: Disjoint set union with randomized linking

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384037)