On the time-space complexity of reachability queries for preprocessed graphs
From MaRDI portal
Publication:916395
DOI10.1016/0020-0190(90)90055-3zbMath0703.68061OpenAlexW2056704770MaRDI QIDQ916395
Lisa Hellerstein, Robert Wilber, Philip N. Klein
Publication date: 1990
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(90)90055-3
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Query time versus redundancy trade-offs for range queries
- Efficient searching using partial ordering
- On the complexity of 2-output Boolean networks
- On the Complexity of Maintaining Partial Sums
- Lower Bounds on the Complexity of Some Optimal Data Structures
- Should Tables Be Sorted?
- A Lower Bound on the Complexity of Orthogonal Range Queries
- The Complexity of Maintaining an Array and Computing Its Partial Sums