On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem

DOI10.1137/0215072MaRDI QIDQ3756517zbMATH OpenOpenAlexFDO

Authors Norbert Blum

Publication date 1986

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

algorithmdata structuredisjoint set union problemlower boundtime complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 3907792
• A lower bound on the single-operation worst-case time complexity of the union-find problem on intervals
• A linear-time algorithm for a special case of disjoint set union
• The complexity of unions of disjoint sets
• The Complexity of Unions of Disjoint Sets
• Worst-case Analysis of Set Union Algorithms
• Worst-case analysis of the set-union problem with extended backtracking
• A randomized concurrent algorithm for disjoint set union
• Worst-case and amortised optimality in union-find (extended abstract)

Cited in

(20)

• A linear-time algorithm for a special case of disjoint set union
• Worst-case analysis of the set-union problem with extended backtracking
• Maintaining bridge-connected and biconnected components on-line
• A lower bound on the single-operation worst-case time complexity of the union-find problem on intervals
• Recognizing union-find trees is NP-complete
• Intersection reporting on two collections of disjoint sets
• An optimal data structure to handle dynamic environments in non-deterministic computations
• Concurrent disjoint set union
• Recognizing union-find trees built up using union-by-rank strategy is NP-complete
• On the succinct representation of equivalence classes
• Reducing structural changes in van Emde Boas' data structure to the lower bound for the dynamic predecessor problem
• Worst-case and amortised optimality in union-find (extended abstract)
• Efficient algorithms for the temporal precedence problem
• Postorder Disjoint Set Union is Linear
• scientific article; zbMATH DE number 3907792 (Why is no real title available?)
• Worst-case Analysis of Set Union Algorithms
• Persistence, randomization and parallelization: On some combinatorial games and their applications (abstract)
• A randomized concurrent algorithm for disjoint set union
• An output sensitive solution to the set union and intersection problem
• Complexity of algorithm and operations on trees

This page was built for publication: On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem

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