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.


References in zbMATH (referenced in 109 articles , 1 standard article )

Showing results 61 to 80 of 109.
Sorted by year (citations)
  1. Dwork, Cynthia; Feldman, Vitaly; Hardt, Moritz; Pitassi, Toniann; Reingold, Omer; Roth, Aaron Leon: Preserving statistical validity in adaptive data analysis (extended abstract) (2015)
  2. Elkin, Michael; Filtser, Arnold; Neiman, Ofer: Prioritized metric structures and embedding (2015)
  3. Fearnley, John; Savani, Rahul: The complexity of the simplex method (2015)
  4. Feldman, Vitaly; Perkins, Will; Vempala, Santosh: On the complexity of random satisfiability problems with planted solutions (extended abstract) (2015)
  5. Fox, Kyle; Klein, Philip N.; Mozes, Shay: A polynomial-time bicriteria approximation scheme for planar bisection (2015)
  6. Ganor, Anat; Kol, Gillat; Raz, Ran: Exponential separation of information and communication for Boolean functions (extended abstract) (2015)
  7. Garg, Sanjam; Lu, Steve; Ostrovsky, Rafail; Scafuro, Alessandra: Garbled RAM from one-way functions (2015)
  8. Ge, Rong; Huang, Qingqing; Kakade, Sham M.: Learning mixtures of Gaussians in high dimensions (2015)
  9. Giakkoupis, George; Helmi, Maryam; Higham, Lisa; Woelfel, Philipp: Test-and-set in optimal space (2015)
  10. Göös, Mika; Lovett, Shachar; Meka, Raghu; Watson, Thomas; Zuckerman, David: Rectangles are nonnegative juntas (2015)
  11. Gorbunov, Sergey; Vaikuntanathan, Vinod; Wichs, Daniel: Leveled fully homomorphic signatures from standard lattices (2015)
  12. Gowers, Timothy; Viola, Emanuele: The communication complexity of interleaved group products (2015)
  13. Grohe, Martin; Schweitzer, Pascal: Computing with tangles (2015)
  14. Gupta, Anupam; Kumar, Amit: Greedy algorithms for Steiner forest (2015)
  15. Halldorsson, Magnus M.; Tonoyan, Tigran: How well can graphs represent wireless interference? (2015)
  16. Hansen, Thomas Dueholm; Zwick, Uri: An improved version of the random-facet pivoting rule for the simplex algorithm (2015)
  17. Hardt, Moritz; Price, Eric: Tight bounds for learning a mixture of two Gaussians (extended abstract) (2015)
  18. Henzinger, Monika; Krinninger, Sebastian; Nanongkai, Danupon; Saranurak, Thatchaphol: Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture (2015)
  19. Kawarabayashi, Ken-ichi; Kreutzer, Stephan: The directed grid theorem (2015)
  20. Kawarabayashi, Ken-ichi; Sidiropoulos, Anastasios: Beyond the Euler characteristic: approximating the genus of general graphs (extended abstract) (2015)