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 structurelower boundtime complexitydisjoint set union problem

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)

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

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)