New lower and upper bounds for representing sequences

DOI10.1007/978-3-642-33090-2_17MaRDI QIDQ2912840zbMATH OpenOpenAlexFDO

Authors Djamal Belazzougui, Gonzalo Navarro

Publication date 25 September 2012

Published in Algorithms – ESA 2012 (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10533/144168

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Quantum algorithms and complexity in the theory of computing (68Q12) Connectivity (05C40)

Recommendations

• Optimal lower and upper bounds for representing sequences
• Optimal lower bounds for rank and select indexes
• Optimal Lower Bounds for Rank and Select Indexes
• Efficient fully-compressed sequence representations

Cited in

(19)

• Linear-space data structures for range frequency queries on arrays and trees
• Space-efficient substring occurrence estimation
• Succinct representation of labeled trees
• Colored range queries and document retrieval
• Compressed string dictionary search with edit distance one
• Efficient fully-compressed sequence representations
• Compressed Data Structures for Dynamic Sequences
• Engineering a lightweight external memory suffix array construction algorithm
• A new lower bound on the family complexity of Legendre sequences
• GLOUDS: representing tree-like graphs
• New space/time tradeoffs for top-\(k\) document retrieval on sequences
• Fast Compressed Self-Indexes with Deterministic Linear-Time Construction
• Succinct encoding of arbitrary graphs
• New Extensions and Applications of Welch-Bound-Equality Sequence Sets
• Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
• A framework for succinct labeled ordinal trees over large alphabets
• Optimal lower and upper bounds for representing sequences
• Wavelet trees for all
• Length lower bounds for reflecting sequences and universal traversal sequences

This page was built for publication: New lower and upper bounds for representing sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2912840)