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 107 articles , 1 standard article )

Showing results 81 to 100 of 107.
Sorted by year (citations)
  1. Koppula, Venkata; Lewko, Allison Bishop; Waters, Brent: Indistinguishability obfuscation for Turing machines with unbounded memory (2015)
  2. Korula, Nitish; Mirrokni, Vahab; Zadimoghaddam, Morteza: Online submodular welfare maximization: greedy beats 1/2 in random order (2015)
  3. Kothari, Pravesh K.; Meka, Raghu: Almost optimal pseudorandom generators for spherical caps (extended abstract) (2015)
  4. Łącki, Jakub; Oćwieja, Jakub; Pilipczuk, Marcin; Sankowski, Piotr; Zych, Anna: The power of dynamic distance oracles, efficient dynamic algorithms for the Steiner tree (2015)
  5. Larsen, Kasper Green; Nelson, Jelani; Nguyên, Huy L.: Time lower bounds for nonadaptive turnstile streaming algorithms (2015)
  6. Lee, Euiwoong: Hardness of graph pricing through generalized Max-Dicut (2015)
  7. Lee, James R.; Raghavendra, Prasad; Steurer, David: Lower bounds on the size of semidefinite programming relaxations (2015)
  8. Li, Jian; Rabani, Yuval; Schulman, Leonard J.; Swamy, Chaitanya: Learning arbitrary statistical mixtures of discrete distributions (2015)
  9. Liu, Jingcheng; Lu, Pinyan: FPTAS for #BIS with degree bounds on one side (2015)
  10. Louis, Anand: Hypergraph Markov operators, eigenvalues and approximation algorithms (2015)
  11. Lovett, Shachar; Zhang, Jiapeng: Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions (2015)
  12. Meka, Raghu; Potechin, Aaron; Wigderson, Avi: Sum-of-squares lower bounds for planted clique (extended abstract) (2015)
  13. Mirrokni, Vahab; Zadimoghaddam, Morteza: Randomized composable core-sets for distributed submodular maximization (2015)
  14. Moitra, Ankur: Super-resolution, extremal functions and the condition number of Vandermonde matrices (2015)
  15. Mossel, Elchanan; Neeman, Joe; Sly, Allan: Consistency thresholds for the planted bisection model (2015)
  16. Mulzer, Wolfgang; Nguyên, Huy L.; Seiferth, Paul; Stein, Yannik: Approximate (k)-flat nearest neighbor search (2015)
  17. Nikolov, Aleksandar: Randomized rounding for the largest simplex problem (2015)
  18. O’Donnell, Ryan; Wright, John: Quantum spectrum testing (2015)
  19. Rubinstein, Aviad: Inapproximability of Nash equilibrium (2015)
  20. Schulman, Leonard J.; Sinclair, Alistair: Analysis of a classical matrix preconditioning algorithm (2015)