A Lower Bound on the Complexity of the Union-Split-Find Problem
From MaRDI portal
Publication:3832045
DOI10.22028/D291-26127 10.1137/0217070; 10.22028/D291-26127zbMath0676.68015OpenAlexW2032259169MaRDI QIDQ3832045
Kurt Mehlhorn, Helmut Alt, Stefan 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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
A lower bound on the single-operation worst-case time complexity of the union-find problem on intervals, 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, A note on predecessor searching in the pointer machine model, A note on set union with arbitrary deunions, The set union problem with dynamic weighted backtracking, Optimal bounds for the predecessor problem and related problems
