Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1145/314464.314496 | Symposium on Discrete Algorithms |
Keywords | Field | DocType |
sequences.,derandomization,algorithms,polylogarithmic time,randomization,dynamic sequence,data structures,convexity,data structure,computational geometry,assignment problem,linear time,random sequence | Discrete mathematics,Binary logarithm,Data structure,Combinatorics,Convexity,Computational geometry,Quadrangle inequality,Assignment problem,Time complexity,Mathematics | Conference |
ISBN | Citations | PageRank |
0-89871-329-3 | 9 | 0.92 |
References | Authors | |
6 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kurt Mehlhorn | 1 | 5314 | 853.36 |
| R. Sundar | 2 | 9 | 0.92 |
| Christian Uhrig | 3 | 739 | 99.73 |