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

DOI10.1137/0215072zbMATH Open0619.68039OpenAlexW2067411846MaRDI QIDQ3756517FDOQ3756517

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

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)

zbMATH Keywords

algorithmdata structurelower boundtime complexitydisjoint set union problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (15)

• Worst-case Analysis of Set Union Algorithms
• 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
• Postorder Disjoint Set Union is Linear
• Worst-case analysis of the set-union problem with extended backtracking
• Title not available (Why is that?)
• A lower bound on the single-operation worst-case time complexity of the union-find problem on intervals
• Persistence, randomization and parallelization: On some combinatorial games and their applications (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)