MAINTAINING DYNAMIC SEQUENCES UNDER EQUALITY TESTS IN POLYLOGARITHMICTIME

Authors
MEHLHORN K SUNDAR R UHRIG C
Citation
K. Mehlhorn et al., MAINTAINING DYNAMIC SEQUENCES UNDER EQUALITY TESTS IN POLYLOGARITHMICTIME, Algorithmica, 17(2), 1997, pp. 183-198
Citations number
7
Categorie Soggetti
Computer Sciences",Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Algorithmica → ACNP
ISSN journal
01784617
Volume
17
Issue
2
Year of publication
1997
Pages
183 - 198
Database
ISI
SICI code
0178-4617(1997)17:2<183:MDSUET>2.0.ZU;2-W
Abstract
We present a randomized and a deterministic data structure for maintai ning a dynamic family of sequences under equality tests of pairs of se quences and creations of new sequences by joining or splitting existin g 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 dete rministic solution supports sequence creations in O(log n (log m log m + log n)) time for the mth operation.