MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


Maintaining dynamic sequences under equality-tests in polylogorithmic time

Mehlhorn, Kurt and Uhrig, Christian

July 1993, 17 pages.

Status: available - back from printing

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 $m$--th operation.

  • MPI-I-93-128.pdfMPI-I-93-128.pdfMPI-I-93-128.dvi.gz
  • Attachement: MPI-I-93-128.dvi.gz (25 KBytes); MPI-I-93-128.pdf (124 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Mehlhorn, Kurt and Uhrig, Christian},
  TITLE = {Maintaining dynamic sequences under equality-tests in polylogorithmic time},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-93-128},
  MONTH = {July},
  YEAR = {1993},
  ISSN = {0946-011X},