A Lower Bound on the Complexity of the Union-Split-Find Problem

DOI10.1137/0217070MaRDI QIDQ3832045zbMATH OpenOpenAlexFDO

Authors K. Mehlhorn, Helmut Alt, S. Näher

Publication date 1988

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

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

zbMATH Keywords

complexitylower boundunionpointer machinepriority queueinterval splitting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Lower bounds for the union-find and the split-find problem on pointer machines
• scientific article; zbMATH DE number 857346
• scientific article; zbMATH DE number 4035134
• Lower bounds for union-split-find related problems on random access machines
• A lower bound on the single-operation worst-case time complexity of the union-find problem on intervals

Cited in

(11)

• A note on set union with arbitrary deunions
• scientific article; zbMATH DE number 4035134 (Why is no real title available?)
• Unifications, deunifications, and their complexity
• A note on predecessor searching in the pointer machine model
• Lower bounds for intersection searching and fractional cascading in higher dimension
• Reducing structural changes in van Emde Boas' data structure to the lower bound for the dynamic predecessor problem
• Lower bounds for union-split-find related problems on random access machines
• scientific article; zbMATH DE number 4062611 (Why is no real title available?)
• A lower bound on the single-operation worst-case time complexity of the union-find problem on intervals
• Optimal bounds for the predecessor problem and related problems
• The set union problem with dynamic weighted backtracking

This page was built for publication: A Lower Bound on the Complexity of the Union-Split-Find Problem

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