Linear expected time of a simple union-find algorithm

DOI10.1016/0020-0190(76)90061-2zbMath0345.68024OpenAlexW1989351810MaRDI QIDQ1233316

Ronald L. Rivest, Jon Doyle

Publication date: 1976

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(76)90061-2

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items (5)

Note on the heights of random recursive trees and random m‐ary search trees ⋮ Applications of the theory of records in the study of random trees ⋮ A class of algorithms which require nonlinear time to maintain disjoint sets ⋮ The expected linearity of a simple equivalence algorithm ⋮ A linear-time algorithm for a special case of disjoint set union

Cites Work

• Efficiency of a Good But Not Linear Set Union Algorithm
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Linear expected time of a simple union-find algorithm