Graphs
Shortest-path queries in static networks. We consider the point-to-point (approximate) shortest-path query problem, which is the following generalization of the classical single-source (SSSP) and all-pairs shortest-path (APSP) problems: we are first presented with a network (graph). A so-called preprocessing algorithm may compute certain information (a data structure or index) to prepare for the next phase. After this preprocessing step, applications may ask shortest-path or distance queries, which should be answered as fast as possible. Due to its many applications in areas such as transportation, networking, and social science, this problem has been considered by researchers from various communities (sometimes under different names): algorithm engineers construct fast route planning methods; database and information systems researchers investigate materialization tradeoffs, query processing on spatial networks, and reachability queries; and theoretical computer scientists analyze distance oracles and sparse spanners. Related problems are considered for compact routing and distance labeling schemes in networking and distributed computing and for metric embeddings in geometry as well. In this survey, we review selected approaches, algorithms, and results on shortest-path queries from these fields, with the main focus lying on the tradeoff between the index size and the query time. We survey methods for general graphs as well as specialized methods for restricted graph classes, in particular for those classes with arguable practical significance such as planar graphs and complex networks.
Keywords for this software
References in zbMATH (referenced in 107 articles , 1 standard article )
Showing results 1 to 20 of 107.
Sorted by year (- Henzinger, Monika; Krinninger, Sebastian; Nanongkai, Danupon: A deterministic almost-tight distributed algorithm for approximating single-source shortest paths (2021)
- Ahmed, Reyan; Bodwin, Greg; Sahneh, Faryad Darabi; Hamm, Keaton; Jebelli, Mohammad Javad Latifi; Kobourov, Stephen; Spence, Richard: Graph spanners: a tutorial review (2020)
- Gu, Qian-Ping; Xu, Gengchun: Constant query time ((1 + \epsilon))-approximate distance oracle for planar graphs (2019)
- Halman, Nir; Kovalyov, Mikhail Y.; Quilliot, Alain; Shabtay, Dvir; Zofi, Moshe: Bi-criteria path problem with minimum length and maximum survival probability (2019)
- Laish, Itay; Mozes, Shay: Efficient dynamic approximate distance oracles for vertex-labeled planar graphs (2019)
- Ahmed, Aly; Thomo, Alex: Computing source-to-target shortest paths for complex networks in RDBMS (2017)
- Jindal, Gorav; Kolev, Pavel; Peng, Richard; Sawlani, Saurabh: Density independent algorithms for sparsifying (k)-step random walks (2017)
- Kontogiannis, Spyros; Zaroliagis, Christos: Distance oracles for time-dependent networks (2016)
- Wei-Kleiner, Fang: Tree decomposition-based indexing for efficient shortest path and nearest neighbors query answering on graphs (2016)
- Aaronson, Scott; Ambainis, Andris: Forrelation: a problem that optimally separates quantum from classical computing (2015)
- Abbe, Emmanuel; Shpilka, Amir; Wigderson, Avi: Reed-Muller codes for random erasures and errors (2015)
- Abboud, Amir; Vassilevska Williams, Virginia; Yu, Huacheng: Matching triangles and basing hardness on an extremely popular conjecture (2015)
- Abdullah, Amirali; Venkatasubramanian, Suresh: A directed isoperimetric inequality with application to Bregman near neighbor lower bounds (2015)
- Abraham, Ittai; Dolev, Danny: Byzantine agreement with optimal early stopping, optimal resilience and polynomial complexity (2015)
- Aggarwal, Divesh; Dadush, Daniel; Regev, Oded; Stephens-Davidowitz, Noah: Solving the shortest vector problem in (2^n) time using discrete Gaussian sampling (extended abstract) (2015)
- Aggarwal, Divesh; Dodis, Yevgeniy; Kazana, Tomasz; Obremski, Maciej: Non-malleable reductions and applications (2015)
- Allen-Zhu, Zeyuan; Liao, Zhenyu; Orecchia, Lorenzo: Spectral sparsification and regret minimization beyond matrix multiplicative updates (2015)
- Allen-Zhu, Zeyuan; Orecchia, Lorenzo: Nearly-linear time positive LP solver with faster convergence rate (2015)
- Alstrup, Stephen; Kaplan, Haim; Thorup, Mikkel; Zwick, Uri: Adjacency labeling schemes and induced-universal graphs (2015)
- Alwen, Joël; Serbinenko, Vladimir: High parallel complexity graphs and memory-hard functions (2015)