Maintaining dynamic sequences under equality tests in polylogarithmic time | Zendy

Kurt Mehlhorn | Zendy; R. Sundar | Zendy; Christian Uhrig | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Maintaining dynamic sequences under equality tests in polylogarithmic time

Author(s) -

Kurt Mehlhorn,

R. Sundar,

Christian Uhrig

Publication year - 1997

Publication title -

algorithmica

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.647

H-Index - 78

eISSN - 1432-0541

pISSN - 0178-4617

DOI - 10.1007/bf02522825

Subject(s) - sequence (biology) , theory of computation , combinatorics , mathematics , randomized algorithm , time complexity , deterministic algorithm , algorithm , genetics , biology

. 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, mClog n// time for the mth operation. Key Words. Algorithms, Data structures, Derandomization, Randomization, Sequences.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research