On the time-space complexity of reachability queries for preprocessed graphs

DOI10.1016/0020-0190(90)90055-3MaRDI QIDQ916395zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

computational complexitypreprocessinggraph reachabilitytime-space trade-offs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 4117855
• Parallelism, Preprocessing, and Reachability: A Hybrid Algorithm for Directed Graphs
• Compact oracles for reachability and approximate distances in planar digraphs
• PReaCH: a fast lightweight reachability index using pruning and contraction hierarchies
• Connectivity oracles for graphs subject to vertex failures

Cites work

• A Lower Bound on the Complexity of Orthogonal Range Queries
• Efficient searching using partial ordering
• Lower Bounds on the Complexity of Some Optimal Data Structures
• On the Complexity of Maintaining Partial Sums
• On the complexity of 2-output Boolean networks
• Query time versus redundancy trade-offs for range queries
• Should Tables Be Sorted?
• The Complexity of Maintaining an Array and Computing Its Partial Sums

Cited in

(5)

• REACHABILITY ON SUFFIX TREE GRAPHS
• O'Reach: Even Faster Reachability in Large Graphs
• PReaCH: a fast lightweight reachability index using pruning and contraction hierarchies
• Space complexity of reachability testing in labelled graphs
• Space Complexity of Reachability Testing in Labelled Graphs

This page was built for publication: On the time-space complexity of reachability queries for preprocessed graphs

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