Dynamic path queries in linear space
From MaRDI portal
Publication:1799220
DOI10.1007/s00453-018-0413-xzbMath1401.68052OpenAlexW2791838006MaRDI QIDQ1799220
Meng He, J. Ian Munro, Gelin Zhou
Publication date: 18 October 2018
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-018-0413-x
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Space efficient data structures for dynamic orthogonal range counting
- A framework for succinct labeled ordinal trees over large alphabets
- On Cartesian trees and range minimum queries
- Towards optimal range medians
- A survey on tree edit distance and related problems
- Orthogonal range searching in linear and almost-linear space
- Computing on a free tree via complexity-preserving mappings
- Succinct representations of weighted trees supporting path queries
- Succinct Representation of Balanced Parentheses and Static Trees
- Fully Functional Static and Dynamic Succinct 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
- Path Queries in Weighted Trees
- Dynamic Range Selection in Linear Space
- Succinct ordinal trees based on tree covering
- Path Minima in Incremental Unrooted Trees
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
- A Data Structure for Dynamically Maintaining Rooted Trees
- Optimal External Memory Interval Management
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
- Optimal Dynamic Sequence Representations
- Path Minima Queries in Dynamic Weighted Trees
- Logarithmic Lower Bounds in the Cell-Probe Model