Maintaining dynamic sequences under equality tests in polylogarithmic time


Autoria(s): Mehlhorn, K; Sundar, R; Uhrig, C
Data(s)

01/02/1997

Resumo

We present a randomized and a deterministic data structure for maintaining a dynamic family of sequences under equality tests of pairs of sequences and creations of new sequences by joining or splitting existing sequences. Both data structures support equality tests in O(1) time. The randomized version supports new sequence creations in O(log(2) n) expected time where n is the length of the sequence created. The deterministic solution supports sequence creations in O(log n (log m log* m + log n)) time for the mth operation.

Formato

application/pdf

Identificador

http://eprints.iisc.ernet.in/38293/1/Maintaining_Dynamic_Sequences_under.pdf

Mehlhorn, K and Sundar, R and Uhrig, C (1997) Maintaining dynamic sequences under equality tests in polylogarithmic time. In: Algorithmica, 17 (2). pp. 183-198.

Publicador

Springer

Relação

http://www.springerlink.com/content/m63my0yvcqecy5pv/

http://eprints.iisc.ernet.in/38293/

Palavras-Chave #Computer Science & Automation (Formerly, School of Automation)
Tipo

Journal Article

PeerReviewed