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

DOI10.1137/0217070zbMATH Open0676.68015OpenAlexW2032259169MaRDI QIDQ3832045FDOQ3832045

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

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

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)

Cited In (11)

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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
• A note on set union with arbitrary deunions

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)