zbMATH — the first resource for mathematics

New lower and upper bounds for representing sequences. (English) Zbl 1365.68260
Epstein, Leah (ed.) et al., Algorithms – ESA 2012. 20th annual European symposium, Ljubljana, Slovenia, September 10–12, 2012. Proceeding. Berlin: Springer (ISBN 978-3-642-33089-6/pbk). Lecture Notes in Computer Science 7501, 181-192 (2012).
Summary: Sequence representations supporting queries access, select and rank are at the core of many data structures. There is a considerable gap between different upper bounds, and the few lower bounds, known for such representations, and how they interact with the space used. In this article we prove a strong lower bound for rank, which holds for rather permissive assumptions on the space used, and give matching upper bounds that require only a compressed representation of the sequence. Within this compressed space, operations access and select can be solved within almost-constant time.
For the entire collection see [Zbl 1246.68031].

68Q12 Quantum algorithms and complexity in the theory of computing
05C40 Connectivity
05C85 Graph algorithms (graph-theoretic aspects)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI