TY  - RPRT
T1  - A lower bound for the complexity of the union-split-find problem
T3  - Kaiserslautern ; Saarbrücken : DFKI, 1986
A1  - Mehlhorn,Kurt
A1  - Näher,Stefan
A1  - Alt,Helmut
Y1  - 2011/09/06
N2  - We prove a Theta(loglog n) (i.e. matching upper and lower) bound on the complexity of the Union-Split-Find problem, a variant of the Union-Find problem. Our lower bound holds for all pointer machine algorithms and does not require the separation assumption used in the lower bound arguments of Tarjan [T79] and Blum [B86]. We complement this with a Theta(log n) bound for the Split-Find problem under the separation assumption. This shows that the separation assumption can imply an exponential loss in efficiency.

CY  - Saarbrücken
PB  - Universitäts- und Landesbibliothek
AD  - Postfach 151141, 66041 Saarbrücken
UR  - http://scidok.sulb.uni-saarland.de/volltexte/2011/4194
ER  -