Please use this identifier to cite or link to this item: doi:10.22028/D291-26127
Title: A lower bound for the complexity of the union-split-find problem
Author(s): Mehlhorn, Kurt
Näher, Stefan
Alt, Helmut
Language: English
Year of Publication: 1986
OPUS Source: Kaiserslautern ; Saarbrücken : DFKI, 1986
DDC notations: 004 Computer science, internet
Publikation type: Report
Abstract: 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.
Link to this record: urn:nbn:de:bsz:291-scidok-41946
Series name: Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes
Series volume: 1986/07
Date of registration: 6-Sep-2011
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
fb14_1986_07.pdf2,65 MBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.