From Time to Space: Fast Algorithms That Yield Small and Fast Data Structures
From MaRDI portal
Publication:2848970
DOI10.1007/978-3-642-40273-9_8zbMath1394.68089MaRDI QIDQ2848970
Publication date: 13 September 2013
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-40273-9_8
sorting; permutation; unbounded search; compressed data structures; set union; adaptive (analysis of) algorithms
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Succinct representations of permutations and functions
- Efficient fully-compressed sequence representations
- An almost optimal algorithm for unbounded searching
- Sorting shuffled monotone sequences
- LRM-trees: compressed indices, adaptive sorting, and compressed permutations
- A framework for adaptive sorting
- Sublinear merging and natural mergesort
- Optimal lower bounds for rank and select indexes
- Alphabet-Independent Compressed Text Indexing
- Succinct indexes for strings, binary relations and multilabeled trees
- Measures of Presortedness and Optimal Sorting Algorithms
- Sorting, trees, and measures of order
- Optimal Succinctness for Range Minimum Queries
- Rank/select operations on large alphabets
- Optimal Lower Bounds for Rank and Select Indexes
- Two Probabilistic Results on Merging
- Universal codeword sets and representations of the integers
- Sorting and Searching in Multisets
- Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
- Algorithms and Computation
- Combinatorial Pattern Matching
- COMPRESSED REPRESENTATIONS OF PERMUTATIONS, AND APPLICATIONS
- A Simple Algorithm for Merging Two Disjoint Linearly Ordered Sets