Graphs swMATH ID: 12277 Software Authors: Sommer, Christian Description: 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. Homepage: http://www.sommer.jp/graphs/ Related Software: Algorithm 97; GraphChi; Pregel; OpenStreetMap; Volume; plfit; Vivaldi; DIMACS; WebGraph; KronFit; UbiCrawler; ANF; MetExplore; SNAP; Pajek datasets Referenced in: 109 Publications Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Shortest-path queries in static networks. Zbl 1305.68137Sommer, Christian 2014 all top 5 Referenced by 245 Authors 3 Kawarabayashi, Ken-ichi 3 Lovett, Shachar 3 Meka, Raghu 3 Nanongkai, Danupon 3 Rauch Henzinger, Monika 3 Thorup, Mikkel 2 Aggarwal, Divesh 2 Ambainis, Andris 2 Andoni, Alexandr 2 Bansal, Nikhil 2 Barak, Boaz 2 Braverman, Mark 2 Chen, Xi 2 Cohen, Michael B. 2 Czumaj, Artur 2 Feldman, Vitaly 2 Garg, Sanjam 2 Gu, Qianping 2 Gupta, Anupam 2 Hardt, Moritz 2 Kontogiannis, Spyros C. 2 Kothari, Pravesh K. 2 Krinninger, Sebastian 2 Mirrokni, Vahab S. 2 Mozes, Shay 2 Nelson, Jelani 2 Orecchia, Lorenzo 2 Peng, Richard 2 Razenshteyn, Ilya P. 2 Schulman, Leonard J. 2 Sly, Allan 2 Steurer, David 2 Vaikuntanathan, Vinod 2 Vempala, Santosh S. 2 Wagner, Dorothea 2 Wigderson, Avi 2 Zadimoghaddam, Morteza 2 Zaroliagis, Christos D. 2 Zhu, Zeyuan Allen 2 Zwick, Uri 1 Aaronson, Scott 1 Abbe, Emmanuel 1 Abboud, Amir 1 Abdullah, Amirali 1 Abraham, Ittai 1 Ahmed, Aly 1 Ahmed, Reyan 1 Alstrup, Stephen 1 Alwen, Joël 1 Bačkurs, Artūrs 1 Bacon, Dave Morris 1 Barman, Siddharth 1 Bassily, Raef 1 Bauer, Reinhard 1 Bhattacharya, Sayan 1 Bhowmick, Abhishek 1 Bitansky, Nir 1 Bodwin, Greg 1 Bourgain, Jean 1 Braun, Gábor 1 Bresler, Guy 1 Canetti, Ran 1 Chan, Siu On 1 Chan, Timothy Moon-Yew 1 Chawla, Shuchi 1 Chechik, Shiri 1 Chen, Zitan 1 Christiani, Tobias 1 Chuzhoy, Julia 1 Cole, Richard John 1 Columbus, Tobias 1 Cousins, Benjamin R. 1 Crescenzi, Pierluigi 1 Dadush, Daniel 1 Daniely, Amit 1 De, Anindya K. 1 Delling, Daniel 1 Ding, Jian 1 Dinur, Irit 1 Dirksen, Sjoerd 1 Dodis, Yevgeniy 1 Dolev, Danny 1 Durfee, David 1 Dvir, Zeev 1 Dwork, Cynthia 1 Elder, Sam 1 Elkin, Michael 1 Fearnley, John 1 Filmus, Yuval 1 Filtser, Arnold 1 Flammia, Steven T. 1 Fox, Kyle 1 Ganor, Anat 1 Garg, Ankit 1 Ge, Rong 1 Ghiani, Gianpaolo 1 Giakkoupis, George 1 Gkatzelis, Vasilis 1 Goldberg, Andrew V. 1 Gong, Ye ...and 145 more Authors all top 5 Referenced in 9 Serials 3 Theoretical Computer Science 2 Journal of Computer and System Sciences 2 Algorithmica 1 ACM Computing Surveys 1 SIAM Journal on Computing 1 Computers & Operations Research 1 Theory of Computing Systems 1 OR Spectrum 1 Computer Science Review all top 5 Referenced in 12 Fields 97 Computer science (68-XX) 34 Combinatorics (05-XX) 20 Information and communication theory, circuits (94-XX) 14 Operations research, mathematical programming (90-XX) 8 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 7 Numerical analysis (65-XX) 3 Quantum theory (81-XX) 2 Group theory and generalizations (20-XX) 2 Statistics (62-XX) 1 Number theory (11-XX) 1 Linear and multilinear algebra; matrix theory (15-XX) 1 Statistical mechanics, structure of matter (82-XX) Referencing Publications by Year