Paper by Erik D. Demaine

Reference:

Mihai Bădoiu and Erik D. Demaine, “A Simplified and Dynamic Unified Structure”, in Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN 2004), Lecture Notes in Computer Science, volume 2976, Buenos Aires, Argentina, April 5–8, 2004, pages 466–473.

Abstract:

The unified property specifies that a comparison-based search structure can quickly find an element nearby a recently accessed element. Iacono [Iac01] introduced this property and developed a static search structure that achieves the bound. We present a dynamic search structure that achieves the unified property and that is simpler than Iacono's structure. Among all comparison-based dynamic search structures, our structure has the best proved bound on running time.

Comments:

This paper is also available from SpringerLink.

Copyright:

The paper is \copyright Springer-Verlag.

Length:

The paper is 8 pages.

Availability:

The paper is available in PostScript (154k), gzipped PostScript (61k), and PDF (127k).

See information on file formats.

[Google Scholar search]

Related papers:

Unified_TCS (A Unified Access Bound on Comparison-Based Dynamic Dictionaries)