research-article

Shortest-path queries in static networks

Author:

Christian SommerAuthors Info & Claims

ACM Computing Surveys (CSUR), Volume 46, Issue 4

Article No.: 45, Pages 1 - 31

https://doi.org/10.1145/2530531

Published: 01 March 2014 Publication History

Abstract

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

[1]

I. Abraham, Y. Bartal, and O. Neiman. 2008a. Embedding metric spaces in their intrinsic dimension. In 19th ACM-SIAM Symposium on Discrete Algorithms (SODA). 363--372.

Digital Library

[2]

I. Abraham, D. Delling, A. Fiat, A. V. Goldberg, and R. F. F. Werneck. 2011a. VC-dimension and shortest path algorithms. In 38th International Colloquium on Automata, Languages and Programming (ICALP). 690--699.

Digital Library

[3]

I. Abraham, D. Delling, A. Fiat, A. V. Goldberg, and R. F. F. Werneck. 2012a. HLDB: location-based services in databases. In SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS). 339--348.

Digital Library

[4]

I. Abraham, D. Delling, A. V. Goldberg, and R. F. F. Werneck. 2011b. A hub-based labeling algorithm for shortest paths in road networks. In 10th International Symposium on Experimental Algorithms (SEA). 230--241.

Digital Library

[5]

I. Abraham, D. Delling, A. V. Goldberg, and R. F. F. Werneck. 2012b. Hierarchical hub labelings for shortest paths. In 20th European Symposium on Algorithms (ESA). 24--35.

Digital Library

[6]

I. Abraham, A. Fiat, A. V. Goldberg, and R. F. F. Werneck. 2010. Highway dimension, shortest paths, and provably efficient algorithms. In 21st ACM-SIAM Symposium on Discrete Algorithms (SODA). 782--793.

Digital Library

[7]

I. Abraham and C. Gavoille. 2006. Object location using path separators. In 25th ACM Symposium on Principles of Distributed Computing (PODC). 188--197.

Digital Library

[8]

I. Abraham and C. Gavoille. 2011. On approximate distance labels and routing schemes with affine stretch. In 25th International Symposium on Distributed Computing (DISC). 404--415.

Digital Library

[9]

I. Abraham, C. Gavoille, D. Malkhi, N. Nisan, and M. Thorup. 2008b. Compact name-independent routing with minimum stretch. ACM Transactions on Algorithms 4, 3.

Digital Library

[10]

D. Achlioptas, A. Clauset, D. Kempe, and C. Moore. 2009. On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs. Journal of the ACM 56, 4.

Digital Library

[11]

R. Agarwal. 2013. The space-stretch-time trade-off in distance oracles. Preprint.

[12]

R. Agarwal, M. Caesar, P. B. Godfrey, and B. Y. Zhao. 2012. Shortest paths in less than a millisecond. In 5th Workshop on Online Social Networks (WOSN).

Digital Library

[13]

R. Agarwal and P. B. Godfrey. 2013. Distance oracles for stretch less than 2. In 24th ACM-SIAM Symposium on Discrete Algorithms (SODA). 526--538.

[14]

R. Agarwal, P. B. Godfrey, and S. Har-Peled. 2011. Approximate distance queries and compact routing in sparse graphs. In 30th IEEE International Conference on Computer Communications (INFOCOM). 1754--1762.

[15]

R. Agrawal and H. V. Jagadish. 1989. Materialization and incremental update of path information. In 5th International Conference on Data Engineering (ICDE). 374--383.

Digital Library

[16]

W. Aiello, F. R. K. Chung, and L. Lu. 2000. A random graph model for massive graphs. In 32nd ACM Symposium on Theory of Computing (STOC). 171--180.

Digital Library

[17]

M. Ajtai and R. Fagin. 1990. Reachability is harder for directed than for undirected finite graphs. Journal of Symbolic Logic 55, 1, 113--150. Announced at FOCS 1988.

[18]

S. B. Akers. 1960. The use of Wye-Delta transformations in network simplification. Operations Research 8, 3, 311--323. Announced at Rand Symposium on Mathematical Programming 1959.

Digital Library

[19]

T. Akiba, Y. Iwata, and Y. Yoshida. 2013. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In ACM SIGMOD International Conference on Management of Data (SIGMOD). 349--360.

Digital Library

[20]

T. Akiba, C. Sommer, and K. Kawarabayashi. 2012. Shortest-path queries for complex networks: Exploiting low tree-width outside the core. In 15th International Conference on Extending Database Technology (EDBT). 144--155.

Digital Library

[21]

N. Alon, P. D. Seymour, and R. Thomas. 1990. A separator theorem for nonplanar graphs. Journal of the American Mathematical Society 3, 4, 801--808. Announced at STOC 1990.

[22]

S. R. Arikati, D. Z. Chen, L. P. Chew, G. Das, M. H. M. Smid, and C. D. Zaroliagis. 1996. Planar spanners and approximate shortest path queries among obstacles in the plane. In 4th European Symposium on Algorithms (ESA). 514--528.

Digital Library

[23]

J. Arz, D. Luxen, and P. Sanders. 2013. Transit node routing reconsidered. In 12th International Symposium on Experimental Algorithms (SEA). 55--66.

[24]

B. Awerbuch, B. Berger, L. Cowen, and D. Peleg. 1998. Near-linear time construction of sparse neighborhood covers. SIAM Journal on Computing 28, 1, 263--277.

Digital Library

[25]

M. A. Babenko, A. V. Goldberg, A. Gupta, and V. Nagarajan. 2013. Algorithms for hub label optimization. In 40th International Colloquium on Automata, Languages, and Programming (ICALP). 69--80.

Digital Library

[26]

Z. K. Baker and M. Gokhale. 2007. On the acceleration of shortest path calculations in transportation networks. In 15th IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM). 23--32.

Digital Library

[27]

C. L. Barrett, K. R. Bisset, R. Jacob, G. Konjevod, and M. V. Marathe. 2002. Classical and contemporary shortest path problems in road networks: Implementation and experimental analysis of the TRANSIMS router. In 10th European Symposium on Algorithms (ESA). 126--138.

Digital Library

[28]

Y. Bartal, L.-A. Gottlieb, T. Kopelowitz, M. Lewenstein, and L. Roditty. 2011. Fast, precise and dynamic distance queries. In 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA). 840--853.

Digital Library

[29]

H. Bast. 2009. Car or public transport—two worlds. In Efficient Algorithms, Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday. 355--367.

Digital Library

[30]

H. Bast, S. Funke, D. Matijevic, P. Sanders, and D. Schultes. 2007a. In transit to constant time shortest-path queries in road networks. In 9th Workshop on Algorithm Engineering and Experiments (ALENEX).

[31]

H. Bast, S. Funke, P. Sanders, and D. Schultes. 2007b. Fast routing in road networks with transit nodes. Science 316, 5824, 566.

[32]

S. Baswana, A. Gaur, S. Sen, and J. Upadhyay. 2008. Distance oracles for unweighted graphs: Breaking the quadratic barrier with constant additive error. In 35th International Colloquium on Automata, Languages and Programming (ICALP). 609--621.

Digital Library

[33]

S. Baswana and T. Kavitha. 2010. Faster algorithms for all-pairs approximate shortest paths in undirected graphs. SIAM Journal on Computing 39, 7, 2865--2896.

Digital Library

[34]

S. Baswana and S. Sen. 2006. Approximate distance oracles for unweighted graphs in expected O(n²) time. ACM Transactions on Algorithms 2, 4, 557--577.

Digital Library

[35]

R. Bauer, T. Columbus, B. Katz, M. Krug, and D. Wagner. 2010a. Preprocessing speed-up techniques is hard. In 7th International Conference on Algorithms and Complexity (CIAC). 359--370.

Digital Library

[36]

R. Bauer, T. Columbus, I. Rutter, and D. Wagner. 2013. Search-space size in contraction hierarchies. In 40th International Colloquium on Automata, Languages, and Programming (ICALP). 93--104.

Digital Library

[37]

R. Bauer, G. D'Angelo, D. Delling, and D. Wagner. 2009. The shortcut problem—complexity and approximation. In 35th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM). 105--116.

Digital Library

[38]

R. Bauer and D. Delling. 2009. SHARC: Fast and robust unidirectional routing. ACM Journal of Experimental Algorithmics 14.

Digital Library

[39]

R. Bauer, D. Delling, P. Sanders, D. Schieferdecker, D. Schultes, and D. Wagner. 2010b. Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm. ACM Journal of Experimental Algorithmics 15, 2.3, 1--31.

Digital Library

[40]

A. Berger, D. Delling, A. Gebhardt, and M. Müller-Hannemann. 2009. Accelerating time-dependent multi-criteria timetable information is harder than expected. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS).

[41]

J. Boothroyd. 1967. Algorithms: Author's note on algorithms 22, 23, 24. Computer Journal 10, 3, 306--308.

[42]

J. Bourgain. 1985. On lipschitz embedding of finite metric spaces in Hilbert space. Israel Journal of Mathematics 52, 1--2, 46--52.

[43]

M. H. Bourgoin and E. M. J. Heurgon. 1969. Study and comparison of algorithms of the shortest path through planned experiments. In Project Planning by Network Analysis. 106--118.

[44]

A. Brady and L. Cowen. 2006. Compact routing on power law graphs with additive stretch. In 8th Workshop on Algorithm Engineering and Experiments (ALENEX). 119--128.

[45]

E. Brunel, D. Delling, A. Gemsa, and D. Wagner. 2010. Space-efficient SHARC-routing. In 9th International Symposium on Experimental Algorithms (SEA). 47--58.

Digital Library

[46]

F. Buchholz. 2000. Hierarchische Graphen zur Wegesuche. Ph.D. thesis, Universität Stuttgart.

[47]

F. Buchholz and B. Riedhofer. 1997. Hierarchische Graphen zur kürzesten Wegesuche in planaren Graphen. Tech. rep. 13, Universität Stuttgart.

[48]

V. Bulitko, Y. Björnsson, N. R. Sturtevant, and R. Lawrence. 2010. Real-time heuristic search for pathfinding in video games. In Artificial Intelligence for Computer Games.

[49]

P. Butterworth, A. Otis, and J. Stein. 1991. The GemStone object database management system. Communications of the ACM 34, 10, 64--77.

Digital Library

[50]

S. Cabello. 2012. Many distances in planar graphs. Algorithmica 62, 1--2, 361--381.

Digital Library

[51]

S. Cabello, E. W. Chambers, and J. Erickson. 2012. Multiple-source shortest paths in embedded graphs. arXiv abs/1202.0314.

[52]

L. Cao, X. Zhao, H. Zheng, and B. Y. Zhao. 2011. Atlas: Approximating shortest paths in social graphs. Tech. rep. 2011-09, Department of Computer Science, University of California, Santa Barbara.

[53]

L. Chang, J. X. Yu, L. Qin, H. Cheng, and M. Qiao. 2012. The exact distance to destination in undirected world. VLDB Journal 21, 6, 869--888.

Digital Library

[54]

B. A. Chartres. 1967. Letter concerning Nicholson's paper. Computer Journal 10, 1, 118--119.

[55]

S. Chechik. 2013. Approximate distance oracle with constant query time. arXiv abs/1305.3314.

[56]

D. Z. Chen and J. Xu. 2000. Shortest path queries in planar graphs. In 32nd ACM Symposium on Theory of Computing (STOC). 469--478.

Digital Library

[57]

W. Chen, C. Sommer, S.-H. Teng, and Y. Wang. 2012. A compact routing scheme and approximate distance oracle for power-law graphs. ACM Transactions on Algorithms 9, 1, 4:1--26.

Digital Library

[58]

J. Cheng, Y. Ke, S. Chu, and C. Cheng. 2012. Efficient processing of distance queries in large graphs: a vertex cover approach. In ACM SIGMOD International Conference on Management of Data. 457--468.

Digital Library

[59]

J. Cheng and J. X. Yu. 2009. On-line exact shortest distance query processing. In 12th International Conference on Extending Database Technology (EDBT). 481--492.

Digital Library

[60]

J. Cheng, J. X. Yu, X. Lin, H. Wang, and P. S. Yu. 2006. Fast computation of reachability labeling for large graphs. In 10th International Conference on Extending Database Technology (EDBT). 961--979.

Digital Library

[61]

J. Cheng, J. X. Yu, X. Lin, H. Wang, and P. S. Yu. 2008. Fast computing reachability labelings for large graphs with high compression rate. In 11th International Conference on Extending Database Technology (EDBT). 193--204.

Digital Library

[62]

B. V. Cherkassky, A. V. Goldberg, and T. Radzik. 1996. Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming 73, 129--174.

Digital Library

[63]

L. Chindelevitch, D. Ziemek, A. Enayetallah, R. Randhawa, B. Sidders, C. Brockel, and E. Huang. 2011. Causal reasoning on biological networks: Interpreting transcriptional changes. In 15th International Conference on Research in Computational Molecular Biology (RECOMB). 34--37.

Digital Library

[64]

F. R. K. Chung and L. Lu. 2002. The average distances in random graphs with given expected degrees. Internet Mathematics 99, 15879--15882.

[65]

A. Clauset, C. R. Shalizi, and M. E. J. Newman. 2009. Power-law distributions in empirical data. SIAM Review 51, 4, 661--703.

Digital Library

[66]

E. Cohen. 1998. Fast algorithms for constructing t-spanners and paths with stretch t. SIAM Journal on Computing 28, 1, 210--236.

Digital Library

[67]

E. Cohen, E. Halperin, H. Kaplan, and U. Zwick. 2003. Reachability and distance queries via 2-hop labels. SIAM Journal on Computing 32, 5, 1338--1355.

Digital Library

[68]

H. Cohen and E. Porat. 2010. On the hardness of distance oracle for sparse graph. arXiv abs/1006.1117.

[69]

M. Costa, M. Castro, A. I. T. Rowstron, and P. B. Key. 2004. PIC: Practical internet coordinates for distance estimation. In 24th International Conference on Distributed Computing Systems (ICDCS). 178--187.

Digital Library

[70]

A. Cvetkovski and M. Crovella. 2009. Hyperbolic embedding and routing for dynamic graphs. In 28th IEEE International Conference on Computer Communications (INFOCOM). 1647--1655.

[71]

F. Dabek, R. Cox, F. Kaashoek, and R. Morris. 2004. Vivaldi: a decentralized network coordinate system. In Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM). 15--26.

Digital Library

[72]

G. B. Dantzig. 1960. On the shortest route through a network. Management Science 6, 2, 187--190.

Digital Library

[73]

G. B. Dantzig. 1963. Linear Programming and Extensions. Princeton University Press.

[74]

A. Das Sarma, S. Gollapudi, M. Najork, and R. Panigrahy. 2010. A sketch-based distance oracle for web-scale graphs. In 3rd International Conference on Web Search and Web Data Mining (WSDM). 401--410.

Digital Library

[75]

D. Delling. 2009. Engineering and Augmenting Route Planning Algorithms. Ph.D. thesis, Universität Karlsruhe.

[76]

D. Delling, A. V. Goldberg, A. Nowatzyk, and R. F. Werneck. 2013. PHAST: Hardware-accelerated shortest path trees. Journal of Parallel and Distributed Computing 73, 7, 940--952.

[77]

D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck. 2013a. Customizable Route Planning in Road Networks. Retrieved from http://research.microsoft.com/pubs/198358/crp_web_130724.pdf.

[78]

D. Delling, A. V. Goldberg, I. Razenshteyn, and R. F. F. Werneck. 2011. Graph partitioning with natural cuts. In 25th IEEE International Symposium on Parallel and Distributed Processing (IPDPS). 1135--1146.

Digital Library

[79]

D. Delling, A. V. Goldberg, and R. F. Werneck. 2013b. Hub label compression. In 12th International Symposium on Experimental Algorithms (SEA). 18--29.

[80]

D. Delling, M. Holzer, K. Müller, F. Schulz, and D. Wagner. 2009. High-performance multi-level routing. In The Shortest Path Problem: 9th DIMACS Implementation Challenge. Vol. 74. 73--92.

[81]

D. Delling, P. Sanders, D. Schultes, and D. Wagner. 2009a. Engineering route planning algorithms. In Algorithmics of Large and Complex Networks - Design, Analysis, and Simulation. 117--139.

Digital Library

[82]

D. Delling, P. Sanders, D. Schultes, and D. Wagner. 2009b. Highway hierarchies star. In The Shortest Path Problem: 9th DIMACS Implementation Challenge. Vol. 74. 141--174.

[83]

C. Demetrescu, A. V. Goldberg, and D. S. Johnson. 2008. Implementation challenge for shortest paths. In Encyclopedia of Algorithms.

[84]

E. Demir, C. Aykanat, and B. Barla Cambazoglu. 2008. Clustering spatial networks for aggregate query processing: A hypergraph approach. Information Systems 33, 1, 1--17.

Digital Library

[85]

N. Deo and C.-Y. Pang. 1984. Shortest path algorithms: Taxonomy and annotation. Networks 14, 257--323.

[86]

R. B. Dial, F. Glover, D. Karney, and D. Klingman. 1979. A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees. Networks 9, 215--248.

[87]

E. W. Dijkstra. 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1, 269--271.

Digital Library

[88]

H. Djidjev. 1996. Efficient algorithms for shortest path problems on planar digraphs. In 22nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG). 151--165.

Digital Library

[89]

H. N. Djidjev. 1985. A linear algorithm for partitioning graphs of fixed genus. Serdica. Bulgariacae mathematicae publicationes 11, 4, 369--387.

[90]

H. N. Djidjev and C. Sommer. 2011. Approximate distance queries for weighted polyhedral surfaces. In 19th European Symposium on Algorithms (ESA). 579--590.

Digital Library

[91]

D. Dor, S. Halperin, and U. Zwick. 2000. All-pairs almost shortest paths. SIAM Journal on Computing 29, 5, 1740--1759.

Digital Library

[92]

J. E. Doran. 1967. An approach to automatic problem-solving. Machine Intelligence 1, 105--124.

[93]

S. E. Dreyfus. 1969. An appraisal of some shortest-path algorithms. Operations Research 17, 3, 395--412.

Digital Library

[94]

Z. Dvorak, D. Král, and R. Thomas. 2010. Deciding first-order properties for sparse graphs. In 51st IEEE Symposium on Foundations of Computer Science (FOCS). 133--142.

Digital Library

[95]

M. Enachescu, M. Wang, and A. Goel. 2008. Reducing maximum stretch in compact routing. In 27th IEEE International Conference on Computer Communications (INFOCOM). 336--340.

[96]

D. Eppstein. 1999. Subgraph isomorphism in planar graphs and related problems. Journal of Graph Algorithms and Applications 3, 3.

[97]

D. Eppstein and M. T. Goodrich. 2008. Studying (non-planar) road networks through an algorithmic lens. In 16th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (GIS). 16.

Digital Library

[98]

P. Erdös. 1964. Extremal problems in graph theory. Theory of Graphs and its Applications, Proceedings of the Symposium Held in Smolenice, 29--36.

[99]

B. Eriksson, P. Barford, and R. D. Nowak. 2009. Estimating hop distance between arbitrary host pairs. In 28th IEEE International Conference on Computer Communications (INFOCOM). 801--809.

[100]

J. Fakcharoenphol and S. Rao. 2006. Planar graphs, negative weight edges, shortest paths, and near linear time. Journal of Computer and System Sciences 72, 5, 868--889.

Digital Library

[101]

J. Fakcharoenphol and T. Saranurak. 2010. Improving stretch bound on the Patrascu--Roditty distance oracle. Preprint.

[102]

M. Faloutsos, P. Faloutsos, and C. Faloutsos. 1999. On power-law relationships of the Internet topology. In Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM). 251--262.

Digital Library

[103]

B. A. Farbey, A. H. Land, and J. D. Murchland. 1967. The cascade algorithm for finding all shortest distances in a directed graph. Management Science 14, 1, 19--28.

Digital Library

[104]

E. Feuerstein and A. Marchetti-Spaccamela. 1991. Dynamic algorithms for shortest paths in planar graphs. In 17th International Workshop on Graph-Theoretic Concepts in Computer Science (WG). 187--197.

Digital Library

[105]

R. W. Floyd. 1962. Algorithm 97: Shortest path. Communications of the ACM 5, 6, 345.

Digital Library

[106]

G. N. Frederickson. 1987. Fast algorithms for shortest paths in planar graphs, with applications. SIAM Journal on Computing 16, 6, 1004--1022.

Digital Library

[107]

M. L. Fredman and R. E. Tarjan. 1987. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM 34, 3, 596--615.

Digital Library

[108]

L. Fu, D.-H. Sun, and L. R. Rilett. 2006. Heuristic shortest path algorithms for transportation applications: State of the art. Computers & Operations Research 33, 11, 3324--3343.

Digital Library

[109]

G. Gallo. 1980. Reoptimization procedures in shortest path problems. Rivista di Matematica per le Scienze Economiche e Sociali 3, 3--13.

[110]

C. Gavoille and D. Peleg. 2003. Compact and localized distributed data structures. Distributed Computing 16, 2--3, 111--120.

Digital Library

[111]

C. Gavoille, D. Peleg, S. Pérennes, and R. Raz. 2004. Distance labeling in graphs. Journal of Algorithms 53, 1, 85--112.

Digital Library

[112]

C. Gavoille and C. Sommer. 2011. Sparse spanners vs. compact routing. In 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 225--234.

Digital Library

[113]

R. Geisberger, P. Sanders, D. Schultes, and D. Delling. 2008. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In 7th International Workshop on Experimental Algorithms (WEA). 319--333.

Digital Library

[114]

R. Geisberger, P. Sanders, D. Schultes, and C. Vetter. 2012. Exact routing in large road networks using contraction hierarchies. Transportation Science 46, 3, 388--404.

Digital Library

[115]

H. L. Gelernter. 1963. Realization of a geometry theorem proving machine. Computers and Thought.

[116]

J. R. Gilbert, J. P. Hutchinson, and R. E. Tarjan. 1984. A separator theorem for graphs of bounded genus. Journal of Algorithms 5, 3, 391--407.

Digital Library

[117]

D. E. Gilsinn and C. Witzgall. 1973. A performance comparison of labeling algorithms for calculating shortest path trees. Technical Note 772, National Institute of Standards and Technology.

[118]

A. Goldberg, H. Kaplan, and R. F. F. Werneck. 2006. Reach for A&ast;: Efficient point-to-point shortest path algorithms. In 8th Workshop on Algorithm Engineering and Experiments (ALENEX). 129--143.

[119]

A. V. Goldberg. 2007. Point-to-point shortest path algorithms with preprocessing. In 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM). 88--102.

Digital Library

[120]

A. V. Goldberg and C. Harrelson. 2005. Computing the shortest path: A&ast; search meets graph theory. In 16th ACM-SIAM Symposium on Discrete Algorithms (SODA). 156--165.

Digital Library

[121]

A. V. Goldberg, H. Kaplan, and R. F. Werneck. 2009. Reach for A&ast;: Shortest path algorithms with preprocessing. In The Shortest Path Problem: 9th DIMACS Implementation Challenge. Vol. 74. 93--139.

[122]

A. V. Goldberg, H. Kaplan, and R. F. F. Werneck. 2007. Better landmarks within reach. In 6th International Workshop on Experimental Algorithms (WEA). 38--51.

Digital Library

[123]

A. V. Goldberg and R. F. F. Werneck. 2005. Computing point-to-point shortest paths from external memory. In 7th Workshop on Algorithm Engineering and Experiments (ALENEX). 26--40.

[124]

B. Golden. 1976. Shortest-path algorithms: A comparison. Operations Research 24, 6, 1164--1168.

Digital Library

[125]

R. Goldman, N. Shivakumar, S. Venkatasubramanian, and H. Garcia-Molina. 1998. Proximity search in databases. In 24th International Conference on Very Large Data Bases (VLDB). 26--37.

Digital Library

[126]

A. Gubichev, S. J. Bedathur, S. Seufert, and G. Weikum. 2010. Fast and accurate estimation of shortest paths in large graphs. In 19th ACM Conference on Information and Knowledge Management (CIKM). 499--508.

Digital Library

[127]

J. Gudmundsson, C. Levcopoulos, G. Narasimhan, and M. H. M. Smid. 2008. Approximate distance oracles for geometric spanners. ACM Transactions on Algorithms 4, 1.

Digital Library

[128]

S. Gupta, S. Kopparty, and C. Ravishankar. 2004. Roads, codes, and spatiotemporal queries. In 23rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS). 115--124.

Digital Library

[129]

R. Gutman. 2004. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In 6th Workshop on Algorithm Engineering and Experiments (ALENEX). 100--111.

[130]

S. Har-Peled and M. Mendel. 2006. Fast construction of nets in low-dimensional metrics and their applications. SIAM Journal on Computing 35, 5, 1148--1184.

Digital Library

[131]

P. E. Hart, N. J. Nilsson, and B. R. Raphael. 1968. A formal basis for the heuristic determination of minimum cost paths in graphs. IEEE Transactions of Systems Science and Cybernetics SSC-4, 2, 100--107.

[132]

M. R. Henzinger, P. N. Klein, S. Rao, and S. Subramanian. 1997. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences 55, 1, 3--23.

Digital Library

[133]

J. Herzen, C. Westphal, and P. Thiran. 2011. Scalable routing easy as PIE: A practical isometric embedding protocol. In 19th IEEE International Conference on Network Protocols (ICNP). 49--58.

Digital Library

[134]

L. E. Hitchner. 1968. A comparative investigation of the computational efficiency of shortest path algorithms. Technical Report ORC 68-17, University of California at Berkeley.

[135]

A. J. Hoffman. 1963. On simple linear programming problems. In Symposia in Pure Mathematics VII. 317--327.

[136]

M. Holzer, F. Schulz, and D. Wagner. 2008. Engineering multilevel overlay graphs for shortest-path queries. ACM Journal of Experimental Algorithmics 13.

Digital Library

[137]

M. Holzer, F. Schulz, D. Wagner, and T. Willhalm. 2005. Combining speed-up techniques for shortest-path computations. ACM Journal of Experimental Algorithmics 10.

Digital Library

[138]

S. Honiden, M. E. Houle, C. Sommer, and M. Wolff. 2010. Approximate shortest path queries in graphs using Voronoi duals. Transactions on Computational Science 9, 28--53.

Digital Library

[139]

T. C. Hu. 1968. A decomposition algorithm for shortest paths in a network. Operations Research 16, 1, 91--102.

Digital Library

[140]

T. C. Hu. 1969. Integer Programming and Network Flows. Addison Wesley.

[141]

T. C. Hu and W. T. Torres. 1969. Shortcut in the decomposition algorithm for shortest paths in a network. IBM Journal of Research and Development 13, 4, 387--390.

Digital Library

[142]

T. Ikeda, M.-Y. Hsu, H. Imai, S. Nishimura, H. Shimoura, T. Hashimoto, K. Tenmoku, and K. Mitoh. 1994. A fast algorithm for finding better routes by AI search techniques. In Vehicle Navigation and Information Systems Conference. 291--296.

[143]

G. F. Italiano, Y. Nussbaum, P. Sankowski, and C. Wulff-Nilsen. 2011. Improved algorithms for min cut and max flow in undirected planar graphs. In 43rd ACM Symposium on Theory of Computing (STOC). 313--322.

Digital Library

[144]

R. Jin, Y. Xiang, N. Ruan, and D. Fuhry. 2009. 3-HOP: a high-compression indexing scheme for reachability query. In 35th SIGMOD International Conference on Management of Data (SIGMOD). 813--826.

Digital Library

[145]

R. Jin, Y. Xiang, N. Ruan, and H. Wang. 2008. Efficiently answering reachability queries on very large directed graphs. In 34th ACM SIGMOD International Conference on Management of Data (SIGMOD). 595--608.

Digital Library

[146]

N. Jing, Y.-W. Huang, and E. A. Rundensteiner. 1996. Hierarchical optimization of optimal path finding for transportation applications. In 5th International Conference on Information and Knowledge Management (CIKM). 261--268.

Digital Library

[147]

N. Jing, Y.-W. Huang, and E. A. Rundensteiner. 1998. Hierarchical encoded path views for path query processing: An optimal model and its performance evaluation. IEEE Transactions on Knowledge and Data Engineering 10, 3, 409--432.

Digital Library

[148]

D. B. Johnson. 1977. Efficient algorithms for shortest paths in sparse networks. Journal of the ACM 24, 1, 1--13.

Digital Library

[149]

S. Jung and S. Pramanik. 1996. HiTi graph model of topographical roadmaps in navigation systems. In 12th International Conference on Data Engineering (ICDE). 76--84.

Digital Library

[150]

S. Kannan, M. Naor, and S. Rudich. 1992. Implicit representation of graphs. SIAM Journal on Discrete Mathematics 5, 4, 596--603.

Digital Library

[151]

F. Karinthy. 1929. Lancszemek.

[152]

K. Kawarabayashi, P. N. Klein, and C. Sommer. 2011. Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs. In 38th International Colloquium on Automata, Languages and Programming (ICALP). 135--146.

Digital Library

[153]

K. Kawarabayashi, C. Sommer, and M. Thorup. 2013. More compact oracles for approximate distances in undirected planar graphs. In 24th ACM-SIAM Symposium on Discrete Algorithms (SODA). 550--563.

[154]

M. Kitamura and M. Yamazaki. 1965. On the connection of the two shortest route systems. In 8th Japanese Road Conference. 66--68.

[155]

V. L. Klee. 1964. A “string algorithm” for shortest path in directed networks. Operations Research 12, 3, 428--432.

Digital Library

[156]

P. N. Klein. 2002. Preprocessing an undirected planar network to enable fast approximate distance queries. In 13th ACM-SIAM Symposium on Discrete Algorithms (SODA). 820--827.

Digital Library

[157]

P. N. Klein. 2005. Multiple-source shortest paths in planar graphs. In 16th ACM-SIAM Symposium on Discrete Algorithms (SODA). 146--155.

Digital Library

[158]

P. N. Klein, S. Mozes, and C. Sommer. 2013. Structured recursive separator decompositions for planar graphs in linear time. In 45th ACM Symposium on Theory of Computing (STOC). 505--514.

Digital Library

[159]

P. N. Klein, S. Mozes, and O. Weimann. 2010. Shortest paths in directed planar graphs with negative lengths: A linear-space O(n log²n)-time algorithm. ACM Transactions on Algorithms 6, 2.

Digital Library

[160]

P. N. Klein and S. Subramanian. 1998. A fully dynamic approximation scheme for shortest paths in planar graphs. Algorithmica 22, 3, 235--249.

[161]

J. M. Kleinberg. 2000. Navigation in a small world. Nature 406, 6798, 845.

[162]

J. M. Kleinberg, A. Slivkins, and T. Wexler. 2009. Triangulation and embedding using small sets of beacons. Journal of the ACM 56, 6.

Digital Library

[163]

E. Köhler, R. H. Möhring, and H. Schilling. 2005. Acceleration of shortest path and constrained shortest path computation. In 4th International Workshop on Experimental and Efficient Algorithms (WEA). 126--138.

Digital Library

[164]

L. Kowalik and M. Kurowski. 2006. Oracles for bounded-length shortest paths in planar graphs. ACM Transactions on Algorithms 2, 3, 335--363.

Digital Library

[165]

D. V. Krioukov, K. R. Fall, and X. Yang. 2004. Compact routing on Internet-like graphs. In 23rd IEEE International Conference on Computer Communications (INFOCOM).

[166]

R.-M. Kung, E. N. Hanson, Y. E. Ioannidis, T. K. Sellis, L. D. Shapiro, and M. Stonebraker. 1986. Heuristic search in database systems. In 1st International Workshop on Expert Database Systems. 537--548.

Digital Library

[167]

J. B. H. Kwa. 1989. BS&ast;: An admissible bidirectional staged heuristic search algorithm. Artificial Intelligence 38, 1, 95--109.

Digital Library

[168]

A. H. Land and S. W. Stairs. 1967. The extension of the cascade algorithm to large graphs. Management Science 14, 1, 29--33.

Digital Library

[169]

U. Lauther. 2004. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background. In Geoinformation und Mobilität—von der Forschung zur praktischen Anwendung. Vol. 22. 219--230.

[170]

S. Lim, C. Sommer, E. Nikolova, and D. Rus. 2012. Practical route planning under delay uncertainty: Stochastic shortest path queries. In Robotics: Science and Systems VIII. 249--256.

[171]

R. J. Lipton, D. J. Rose, and R. E. Tarjan. 1979. Generalized nested dissection. SIAM Journal on Numerical Analysis 16, 346--358.

[172]

R. J. Lipton and R. E. Tarjan. 1979. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics 36, 2, 177--189.

Digital Library

[173]

J. Matousek. 1996. On the distortion required for embedding finite metric spaces into normed spaces. Israel Journal of Mathematics 93, 1, 333--344.

[174]

J. Maue, P. Sanders, and D. Matijevic. 2009. Goal-directed shortest-path queries using precomputed cluster distances. ACM Journal of Experimental Algorithmics 14, 3.2--3.27.

Digital Library

[175]

K. Mehlhorn and P. Sanders. 2008. Algorithms and data structures: the basic toolbox. Springer.

Digital Library

[176]

M. Mendel and A. Naor. 2007. Ramsey partitions and proximity data structures. Journal of the European Mathematical Society 9, 2, 253--275.

[177]

M. Mendel and C. Schwob. 2009. Fast C-K-R partitions of sparse graphs. Chicago Journal of Theoretical Computer Science, 1--18.

[178]

S. Milgram. 1967. The small world problem. Psychology Today 1, 61--67.

[179]

G. Mills. 1966. A decomposition algorithm for the shortest route problem. Operations Research 14, 279--286.

Digital Library

[180]

N. Milosavljevic. 2012. On optimal preprocessing for contraction hierarchies. In 5th ACM SIGSPATIAL International Workshop on Computational Transportation Science (IWCTS). 33--38.

Digital Library

[181]

G. J. Minty. 1957. A comment on the shortest-route problem. Operations Research 5, 5, 724.

Digital Library

[182]

R. H. Möhring, H. Schilling, B. Schütz, D. Wagner, and T. Willhalm. 2006. Partitioning graphs to speedup Dijkstra's algorithm. ACM Journal of Experimental Algorithmics 11.

Digital Library

[183]

G. Monge. 1781. Mémoire sur la théorie des déblais et de remblais. Histoire de l'Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année, 666--704.

[184]

E. F. Moore. 1959. The shortest path through a maze. In Annals of the Computation Laboratory of Harvard University. Harvard University Press, 285--292.

[185]

S. Mozes and C. Sommer. 2012. Exact distance oracles for planar graphs. In 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA). 209--222.

Digital Library

[186]

L. F. Muller and M. Zachariasen. 2007. Fast and compact oracles for approximate distances in planar graphs. In 15th European Symposium on Algorithms (ESA). 657--668.

Digital Library

[187]

J. D. Murchland. 1965. A new method for finding all elementary paths in a complete directed graph. Tech. rep. LBS-TNT-22, London Business School, Transport Network Theory Unit.

[188]

J. D. Murchland. 1967. The “once-through” method of finding all shortest distances in a graph from a single origin. Tech. rep. LBS-TNT-56, London Business School, Transport Network Theory Unit.

[189]

J. Nesetril and P. O. de Mendez. 2006. Linear time low tree-width partitions and algorithmic consequences. In 38th ACM Symposium on Theory of Computing (STOC). 391--400.

Digital Library

[190]

M. E. J. Newman. 2001. Scientific collaboration networks. II. shortest paths, weighted networks, and centrality. Physical Review E (Statistical, Nonlinear, and Soft Matter Physics) 64.

[191]

T. S. E. Ng and H. Zhang. 2002. Predicting internet network distance with coordinates-based approaches. In 21st IEEE International Conference on Computer Communications (INFOCOM).

[192]

T. A. J. Nicholson. 1966. Finding the shortest route between two points in a network. The Computer Journal 9, 3, 275--280.

[193]

Y. Nussbaum. 2011. Improved distance queries in planar graphs. In 12th International Symposium on Algorithms and Data Structures (WADS). 642--653.

Digital Library

[194]

D. Papadias, J. Zhang, N. Mamoulis, and Y. Tao. 2003. Query processing in spatial network databases. In 29th International Conference on Very Large Data Bases (VLDB). 802--813.

Digital Library

[195]

F. Papadopoulos, D. V. Krioukov, M. Boguñá, and A. Vahdat. 2010. Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces. In 29th IEEE International Conference on Computer Communications (INFOCOM). 2973--2981.

Digital Library

[196]

U. Pape. 1974. Implementation and efficiency of Moore-algorithms for the shortest route problem. Mathematical Programming 7, 1, 212--222.

Digital Library

[197]

M. Patrascu. 2011. Unifying the landscape of cell-probe lower bounds. SIAM Journal on Computing 40, 3, 827--847.

Digital Library

[198]

M. Patrascu and L. Roditty. 2010. Distance oracles beyond the Thorup-Zwick bound. In 51st IEEE Symposium on Foundations of Computer Science (FOCS). 815--823.

Digital Library

[199]

M. Patrascu, L. Roditty, and M. Thorup. 2012. A new infinity of distance oracles for sparse graphs. In 53rd IEEE Symposium on Foundations of Computer Science (FOCS). 738--747.

Digital Library

[200]

D. Peleg. 2000. Proximity-preserving labeling schemes. Journal of Graph Theory 33, 167--176.

Digital Library

[201]

I. S. Pohl. 1971. Bi-directional search. Machine Intelligence 6, 127--140.

[202]

M. Pollack and W. Wiebenson. 1960. Solutions of the shortest-route problem—a review. Operations Research 8, 2, 224--230.

Digital Library

[203]

E. Porat and L. Roditty. 2013. Preprocess, set, query&excl; Algorithmica 67, 4, 516--528.

[204]

M. Potamias, F. Bonchi, C. Castillo, and A. Gionis. 2009. Fast shortest path distance estimation in large networks. In 18th ACM Conference on Information and Knowledge Management (CIKM). 867--876.

Digital Library

[205]

F. P. Preparata and M. I. Shamos. 1985. Computational geometry: an introduction.

Digital Library

[206]

M. Qiao, H. Cheng, L. Chang, and J. X. Yu. 2012. Approximate shortest distance computing: A query-dependent local landmark scheme. In 28th International Conference on Data Engineering (ICDE).

Digital Library

[207]

M. Qiao, H. Cheng, and J. X. Yu. 2011. Querying shortest path distance with bounded errors in large graphs. In 23rd International Conference on Scientific and Statistical Database Management (SSDBM). 255--273.

Digital Library

[208]

S. A. Rahman, P. Advani, R. Schunk, R. Schrader, and D. Schomburg. 2005. Metabolic pathway analysis web service (Pathway Hunter Tool at CUBIC). Bioinformatics 21, 7, 1189--1193.

Digital Library

[209]

B. Raney and K. Nagel. 2004. Iterative route planning for large-scale modular transportation simulations. Future Generation Computer Systems 20, 7, 1101--1118.

Digital Library

[210]

M. J. Rattigan, M. Maier, and D. Jensen. 2006. Using structure indices for efficient approximation of network properties. In 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). 357--366.

Digital Library

[211]

M. J. Rattigan, M. Maier, and D. Jensen. 2007. Graph clustering with network structure indices. In 24th International Conference on Machine Learning (ICML). 783--790.

Digital Library

[212]

B. Riedhofer. 1997. Hierarchische Straßengraphen. M.S. thesis, Universität Stuttgart.

[213]

L. Roditty, M. Thorup, and U. Zwick. 2005. Deterministic constructions of approximate distance oracles and spanners. In 32nd International Colloquium on Automata, Languages and Programming (ICALP). 261--272.

Digital Library

[214]

M. Roughan, W. Willinger, O. Maennel, D. Perouli, and R. Bush. 2011. 10 lessons from 10 years of measuring and modeling the Internet's autonomous systems. IEEE Journal on Selected Areas in Communications 29, 9, 1810--1821.

[215]

H. Samet, J. Sankaranarayanan, and H. Alborzi. 2008. Scalable network distance browsing in spatial databases. In ACM SIGMOD International Conference on Management of Data (SIGMOD). 43--54.

Digital Library

[216]

A. L. Samuel. 1963. Some studies in machine learning using the game of checkers. Computers and Thought. 3, 211--229.

Digital Library

[217]

P. Sanders. 2009. Algorithm engineering—an attempt at a definition. In Efficient Algorithms, Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday. 321--340.

Digital Library

[218]

P. Sanders and D. Schultes. 2005. Highway hierarchies hasten exact shortest path queries. In 13th European Symposium on Algorithms (ESA). 568--579.

Digital Library

[219]

P. Sanders and D. Schultes. 2006. Engineering highway hierarchies. In 14th European Symposium on Algorithms (ESA). 804--816.

Digital Library

[220]

P. Sanders, D. Schultes, and C. Vetter. 2008. Mobile route planning. In 16th European Symposium on Algorithms (ESA). 732--743.

Digital Library

[221]

J. Sankaranarayanan and H. Samet. 2009. Distance oracles for spatial networks. In 25th International Conference on Data Engineering (ICDE). 652--663.

Digital Library

[222]

J. Sankaranarayanan, H. Samet, and H. Alborzi. 2009. Path oracles for spatial networks. Proceedings of the VLDB Endowment 2, 1, 1210--1221.

Digital Library

[223]

J. L. Santos. 2009. Real-world applications of shortest path algorithms. In The Shortest Path Problem: 9th DIMACS Implementation Challenge. Vol. 74. 1--19.

[224]

R. Schenkel, A. Theobald, and G. Weikum. 2004. HOPI: An efficient connection index for complex XML document collections. In 9th International Conference on Extending Database Technology (EDBT). 237--255.

[225]

R. Schenkel, A. Theobald, and G. Weikum. 2005. Efficient creation and incremental maintenance of the HOPI index for complex XML document collections. In 21st International Conference on Data Engineering (ICDE). 360--371.

Digital Library

[226]

J. P. Schmidt. 1998. All highest scoring paths in weighted grid graphs and their application to finding all approximate repeats in strings. SIAM Journal on Computing 27, 4, 972--992.

Digital Library

[227]

D. Schultes. 2008. Route planning in road networks. Ph.D. thesis, Universität Karlsruhe.

[228]

D. Schultes and P. Sanders. 2007. Dynamic highway-node routing. In 6th International Workshop on Experimental Algorithms (WEA). 66--79.

Digital Library

[229]

F. Schulz, D. Wagner, and C. D. Zaroliagis. 2002. Using multi-level graphs for timetable information in railway systems. In 4th Workshop on Algorithm Engineering and Experiments (ALENEX). 43--59.

Digital Library

[230]

M. Schwartz and T. E. Stern. 1980. Routing techniques used in computer communication networks. IEEE Transactions on Communications 28, 4, 539--552.

[231]

R. Sedgewick and J. S. Vitter. 1986. Shortest paths in Euclidean graphs. Algorithmica 1, 1, 31--48. Announced at FOCS 1984.

Digital Library

[232]

S. Sen. 2009. Approximating shortest paths in graphs. In 3rd International Workshop on Algorithms and Computation (WALCOM). 32--43.

Digital Library

[233]

Y. Shavitt and T. Tankel. 2008. Hyperbolic embedding of internet graph for distance estimation and overlay construction. IEEE/ACM Transactions on Networking 16, 25--36.

Digital Library

[234]

S. Shekhar, A. Fetterer, and B. Goyal. 1997. Materialization trade-offs in hierarchical shortest path algorithms. In 5th International Symposium on Advances in Spatial Databases (SSD). 94--111.

Digital Library

[235]

H. A. Smolleck. 1975. Application of fast sparse-matrix techniques and an energy estimation model for large transportation networks. Ph.D. thesis, University of Texas at Arlington.

[236]

H. A. Smolleck and M.-S. Chen. 1981. A new approach to near-optimal path assignment through electric-circuit modeling. Networks 11, 335--349.

[237]

C. Sommer. 2010. Approximate shortest path and distance queries in networks. Ph.D. thesis, The University of Tokyo.

[238]

C. Sommer, E. Verbin, and W. Yu. 2009. Distance oracles for sparse graphs. In 50th IEEE Symposium on Foundations of Computer Science (FOCS). 703--712.

Digital Library

[239]

B. Stout. 1999. Smart move: Intelligent path-finding. Retrieved from http://www.gamasutra.com/view/feature/3317/smart_move_intelligent_.php.

[240]

M. Thorup. 2004. Compact oracles for reachability and approximate distances in planar digraphs. Journal of the ACM 51, 6, 993--1024.

Digital Library

[241]

M. Thorup and U. Zwick. 2001. Compact routing schemes. In ACM Symposium on Parallelism in Algorithms and Architectures. 1--10.

Digital Library

[242]

M. Thorup and U. Zwick. 2005. Approximate distance oracles. Journal of the ACM 52, 1, 1--24.

Digital Library

[243]

K. Tretyakov, A. Armas-Cervantes, L. García-Bañuelos, J. Vilo, and M. Dumas. 2011. Fast fully dynamic landmark-based estimation of shortest path distances in very large graphs. In 20th ACM Conference on Information and Knowledge Management (CIKM). 1785--1794.

Digital Library

[244]

P. Ungar. 1951. A theorem on planar graphs. Journal of the London Mathematical Societys 1--26, 4, 256--262.

[245]

D. van Vliet. 1978. Improved shortest path algorithms for transport networks. Transportation Research 12, 1, 7--20.

[246]

M. V. Vieira, B. M. Fonseca, R. Damazio, P. B. Golgher, D. de Castro Reis, and B. A. Ribeiro-Neto. 2007. Efficient search ranking in social networks. In 16th ACM Conference on Information and Knowledge Management (CIKM). 563--572.

Digital Library

[247]

D. Wagner and T. Willhalm. 2003. Geometric speed-up techniques for finding shortest paths in large sparse graphs. In 11th European Symposium on Algorithms (ESA). 776--787.

[248]

D. Wagner and T. Willhalm. 2005. Drawing graphs to speed up shortest-path computations. In 7th Workshop on Algorithm Engineering and Experiments (ALENEX). 17--25.

[249]

D. Wagner and T. Willhalm. 2007. Speed-up techniques for shortest-path computations. In 24th Symposium on Theoretical Aspects of Computer Science (STACS). 23--36.

Digital Library

[250]

D. Wagner, T. Willhalm, and C. D. Zaroliagis. 2005. Geometric containers for efficient shortest-path computation. ACM Journal of Experimental Algorithmics 10.

Digital Library

[251]

S. Warshall. 1962. A theorem on boolean matrices. Journal of the ACM 9, 1, 11--12.

Digital Library

[252]

F. Wei. 2010. TEDI: efficient shortest path query answering on graphs. In ACM SIGMOD International Conference on Management of Data (SIGMOD). 99--110.

Digital Library

[253]

C. Wulff-Nilsen. 2010. Algorithms for planar graphs and graphs in metric spaces. Ph.D. thesis, University of Copenhagen.

[254]

C. Wulff-Nilsen. 2012. Approximate distance oracles with improved preprocessing time. In 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA). 202--208.

Digital Library

[255]

C. Wulff-Nilsen. 2013. Approximate distance oracles with improved query time. In 24th ACM-SIAM Symposium on Discrete Algorithms (SODA). 539--549.

[256]

A. C.-C. Yao. 1981. Should tables be sorted&quest; Journal of the ACM 28, 3, 615--628.

Digital Library

[257]

C. Zaroliagis. 2008. Engineering algorithms for large network applications. In Encyclopedia of Algorithms.

[258]

F. B. Zhan and C. E. Noon. 1998. Shortest path algorithms: An evaluation using real road networks. Transportation Science 32, 1, 65--73.

Digital Library

[259]

X. Zhao, A. Sala, C. Wilson, H. Zheng, and B. Y. Zhao. 2010. Orion: shortest path estimation for large social graphs. In 3rd Conference on Online Social Networks (WOSN). 9--9.

Digital Library

[260]

X. Zhao, A. Sala, H. Zheng, and B. Y. Zhao. 2011. Efficient shortest paths on massive social graphs. In 7th International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom). 77--86.

[261]

A. K. Ziliaskopoulos, D. Kotzinos, and H. S. Mahmassani. 1997. Design and implementation of parallel time-dependent least time path algorithms for intelligent transportation systems applications. Transportation Research Part C: Emerging Technologies 5, 2, 95--107.

[262]

U. Zwick. 2001. Exact and approximate distances in graphs—a survey. In 9th European Symposium on Algorithms (ESA). 33--48.

Digital Library

Cited By

Cao ZCao CXu JXu JChen ZChen ZMa X(2025)SCG-tree: shortcut enhanced graph hierarchy tree for efficient spatial queries on massive road networksFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-024-40459-x19:9Online publication date: 1-Sep-2025
https://dl.acm.org/doi/10.1007/s11704-024-40459-x
Dreyer SGenitrini ANaima M(2025)Optimal Uniform Shortest Path SamplingWALCOM: Algorithms and Computation10.1007/978-981-96-2845-2_11(160-179)Online publication date: 21-Feb-2025
https://doi.org/10.1007/978-981-96-2845-2_11
Masha AAgyeman N(2024)An Analysis of Must-be Attributes of Off-campus Student Housing Facilities and their Influence on Effective Learning: The Case of One University in South AfricaE-Journal of Humanities, Arts and Social Sciences10.38159/ehass.202451657(3391-3406)Online publication date: 30-Dec-2024
https://doi.org/10.38159/ehass.202451657
Show More Cited By

Index Terms

Shortest-path queries in static networks
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

A Multiple Pairs Shortest Path Algorithm

The multiple pairs shortest path problem (MPSP) arises in many applications where the shortest paths and distances between only some specific pairs of origin-destination (OD) nodes in a network are desired. The traditional repeated single-source shortest ...
Algorithms for Approximate Shortest Path Queries on Weighted Polyhedral Surfaces

We consider the well-known geometric problem of determining shortest paths between pairs of points on a polyhedral surface P, where P consists of triangular faces with positive weights assigned to them. The cost of a path in P is defined to be the ...
An Algorithm to Find the kth Shortest Path in Halin Networks
IITAW '08: Proceedings of the 2008 International Symposium on Intelligent Information Technology Application Workshops

K shortest path problem finds the kth shortest path from the source node to the destination node. It’s known that the k shortest path problem is NP-complete. In this paper, we restrict the problem in Halin Networks and give an algorithm to find the kth ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Computing Surveys

ACM Computing Surveys Volume 46, Issue 4

April 2014

463 pages

ISSN:0360-0300

EISSN:1557-7341

DOI:10.1145/2597757

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 2014

Accepted: 01 September 2013

Revised: 01 September 2013

Received: 01 June 2012

Published in CSUR Volume 46, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

158
Total Citations
View Citations
2,586
Total Downloads

Downloads (Last 12 months)203
Downloads (Last 6 weeks)15

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cao ZCao CXu JXu JChen ZChen ZMa X(2025)SCG-tree: shortcut enhanced graph hierarchy tree for efficient spatial queries on massive road networksFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-024-40459-x19:9Online publication date: 1-Sep-2025
https://dl.acm.org/doi/10.1007/s11704-024-40459-x
Dreyer SGenitrini ANaima M(2025)Optimal Uniform Shortest Path SamplingWALCOM: Algorithms and Computation10.1007/978-981-96-2845-2_11(160-179)Online publication date: 21-Feb-2025
https://doi.org/10.1007/978-981-96-2845-2_11
Masha AAgyeman N(2024)An Analysis of Must-be Attributes of Off-campus Student Housing Facilities and their Influence on Effective Learning: The Case of One University in South AfricaE-Journal of Humanities, Arts and Social Sciences10.38159/ehass.202451657(3391-3406)Online publication date: 30-Dec-2024
https://doi.org/10.38159/ehass.202451657
Tang JGong SZhang YFu CYu G(2024)Distributed Single-Source Shortest Path with Only Local RelaxationElectronics10.3390/electronics1313250213:13(2502)Online publication date: 26-Jun-2024
https://doi.org/10.3390/electronics13132502
van der Hagen LAgatz NSpliet RVisser TKok L(2024)Machine Learning–Based Feasibility Checks for Dynamic Time Slot ManagementTransportation Science10.1287/trsc.2022.118358:1(94-109)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1287/trsc.2022.1183
Hung KZhang CYankov D(2024)Customizable Routing with Learnings from Past RecommendationsProceedings of the 32nd ACM International Conference on Advances in Geographic Information Systems10.1145/3678717.3691327(489-492)Online publication date: 29-Oct-2024
https://dl.acm.org/doi/10.1145/3678717.3691327
Wang SChu WSu LYang JZhu JHuang Y(2024)Fast Landmark-Based Optimal Routing for BGP-ORR ProtocolProceedings of the 2024 5th International Conference on Computing, Networks and Internet of Things10.1145/3670105.3670118(74-80)Online publication date: 24-May-2024
https://dl.acm.org/doi/10.1145/3670105.3670118
Yang MLi WWang WWen DQin L(2024)Querying Numeric-Constrained Shortest Distances on Road Networks2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00194(2463-2475)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00194
Luo YChen BZhang YLi WGong JLi Q(2024)Space-time tree: a spatiotemporal construct for efficient similarity matrix calculations among network-constrained trajectoriesInternational Journal of Geographical Information Science10.1080/13658816.2024.2431906(1-36)Online publication date: 2-Dec-2024
https://doi.org/10.1080/13658816.2024.2431906
Erfan Doraki MAvami ABoroushaki MAmini Z(2024)Agent-Based Modeling for Sustainable Urban Passenger Vehicle Mobility: A Case of TehranTransportation Research Part D: Transport and Environment10.1016/j.trd.2024.104380135(104380)Online publication date: Oct-2024
https://doi.org/10.1016/j.trd.2024.104380
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents