Succinct indices for path minimum, with applications
From MaRDI portal
Publication:2362355
DOI10.1007/s00453-016-0170-7zbMath1369.68167OpenAlexW2414522820MaRDI QIDQ2362355
Gelin Zhou, Meng He, Timothy M. Chan, J. Ian Munro
Publication date: 7 July 2017
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-016-0170-7
succinct data structurespath minimumpath reportingsemigroup path sumsuccinct encoding of directed topology trees
Related Items (4)
Shortest beer path queries in outerplanar graphs ⋮ Unnamed Item ⋮ Tree path majority data structures ⋮ Data structures for categorical path counting queries
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A framework for succinct labeled ordinal trees over large alphabets
- A survey on tree edit distance and related problems
- On space efficient two dimensional range minimum data structures
- An inverse-Ackermann type lower bound for online minimum spanning tree verification
- Linear verification for spanning trees
- Computing on a free tree via complexity-preserving mappings
- A simpler minimum spanning tree verification algorithm
- A data structure for dynamic trees
- Succinct representations of weighted trees supporting path queries
- A uniform paradigm to succinctly encode various families of trees
- Optimal lower bounds for rank and select indexes
- Succinct Representation of Balanced Parentheses and Static Trees
- Linear-Space Data Structures for Range Frequency Queries on Arrays and Trees
- Two Dimensional Range Minimum Queries and Fibonacci Lattices
- Succinct Data Structures for Path Queries
- Succinct Indices for Path Minimum, with Applications to Path Reporting
- Dynamic Path Counting and Reporting in Linear Space
- Succinct ordinal trees with level-ancestor queries
- Compressed representations of sequences and full-text indexes
- Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
- Path Queries in Weighted Trees
- Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
- Succinct indexes for strings, binary relations and multilabeled trees
- Succinct ordinal trees based on tree covering
- THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE
- Fast Algorithms for Finding Nearest Common Ancestors
- Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems
- Path Minima in Incremental Unrooted Trees
- Squeezing succinct data structures into entropy bounds
- On Cartesian Trees and Range Minimum Queries
- Universal Succinct Representations of Trees?
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- A unifying look at data structures
- Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
- Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
- A Data Structure for Dynamically Maintaining Rooted Trees
- A linear lower bound on index size for text retrieval
- Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
- Optimal static range reporting in one dimension
- Path Minima Queries in Dynamic Weighted Trees
- More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries
- Orthogonal range searching on the RAM, revisited
- Succinct sampling from discrete distributions
This page was built for publication: Succinct indices for path minimum, with applications
