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 21 to 40 of 107.
Sorted by year (citations)
  1. Ambainis, Andris; Filmus, Yuval; Le Gall, François: Fast matrix multiplication: limitations of the Coppersmith-Winograd method (extended abstract) (2015)
  2. Andoni, Alexandr; Krauthgamer, Robert; Razenshteyn, Ilya: Sketching and embedding are equivalent for norms (2015)
  3. Andoni, Alexandr; Razenshteyn, Ilya: Optimal data-dependent hashing for approximate near neighbors (2015)
  4. Backurs, Arturs; Indyk, Piotr: Edit distance cannot be computed in strongly subquadratic time (unless SETH is false) (2015)
  5. Bacon, Dave; Flammia, Steven T.; Harrow, Aram W.; Shi, Jonathan: Sparse quantum codes from quantum circuits (2015)
  6. Bansal, Nikhil; Gupta, Anupam; Guruganesh, Guru: On the Lovász theta function for independent sets in sparse graphs (2015)
  7. Bansal, Nikhil; Kulkarni, Janardhan: Minimizing flow-time on unrelated machines (2015)
  8. Barak, Boaz; Chan, Siu On; Kothari, Pravesh K.: Sum of squares lower bounds from pairwise independence (extended abstract) (2015)
  9. Barak, Boaz; Kelner, Jonathan A.; Steurer, David: Dictionary learning and tensor decomposition via the sum-of-squares method (2015)
  10. Barman, Siddharth: Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Carathéodory’s theorem (2015)
  11. Bassily, Raef; Smith, Adam: Local, private, efficient protocols for succinct histograms (2015)
  12. Bhattacharya, Sayan; Henzinger, Monika; Nanongkai, Danupon; Tsourakakis, Charalampos: Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams (2015)
  13. Bhowmick, Abhishek; Lovett, Shachar: The list decoding radius of Reed-Muller codes over small fields (2015)
  14. Bitansky, Nir; Garg, Sanjam; Lin, Huijia; Pass, Rafael; Telang, Sidharth: Succinct randomized encodings and their applications (2015)
  15. Bourgain, Jean; Dirksen, Sjoerd; Nelson, Jelani: Toward a unified theory of sparse dimensionality reduction in Euclidean space (2015)
  16. Braun, Gábor; Pokutta, Sebastian; Zink, Daniel: Inapproximability of combinatorial problems via small LPs and SDPs (2015)
  17. Braverman, Mark; Garg, Ankit: Small value parallel repetition for general games (2015)
  18. Braverman, Mark; Weinstein, Omri: An interactive information odometer and applications (2015)
  19. Bresler, Guy: Efficiently learning Ising models on arbitrary graphs (extended abstract) (2015)
  20. Canetti, Ran; Holmgren, Justin; Jain, Abhishek; Vaikuntanathan, Vinod: Succinct garbling and indistinguishability obfuscation for RAM programs (2015)