Julian Dibbelt
Skip Abstract Section
Abstract
We consider the problem of quickly computing shortest paths in weighted graphs. Often, this is achieved in two phases: (1) derive auxiliary data in an expensive preprocessing phase, and (2) use this auxiliary data to speed up the query phase. By adding a fast weight-customization phase, we extend Contraction Hierarchies to support a three-phase workflow. The expensive preprocessing is split into a phase exploiting solely the unweighted topology of the graph and a lightweight phase that adapts the auxiliary data to a specific weight. We achieve this by basing our Customizable Contraction Hierarchies (CCHs) on nested dissection orders. We provide an in-depth experimental analysis on large road and game maps showing that CCHs are a very practicable solution in scenarios where edge weights often change.
- Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. 2012a. HLDB: Location-based services in databases. In Proceedings of the 20th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (GIS'12). ACM, New York, NY, 339--348. Google Scholar
Digital Library
- Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. 2013a. Highway dimension and provably efficient shortest path algorithms. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'10). 782--793. Google ScholarDigital Library
- Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. 2012b. Hierarchical hub labelings for shortest paths. In Algorithms—ESA 2012. Lecture Notes in Computer Science, Vol. 7501. Springer, 24--35. Google ScholarDigital Library
- Ittai Abraham, Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. 2013b. Alternative routes in road networks. ACM Journal of Experimental Algorithmics 18, 1, 1--17. Google ScholarDigital Library
- Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. 2010. Highway dimension, shortest paths, and provably efficient algorithms. In Proceedings of the 21st Annual ACM--SIAM Symposium on Discrete Algorithms (SODA'10). 782--793. Google ScholarDigital Library
- Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias Müller--Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. 2015. Route Planning in Transportation Networks. Technical Report. arXiv:1504.05140. http://arxiv.org/abs/1504.05140.Google Scholar
- Reinhard Bauer, Tobias Columbus, Bastian Katz, Marcus Krug, and Dorothea Wagner. 2010. Preprocessing speed-up techniques is hard. In Algorithms and Complexity. Lecture Notes in Computer Science, Vol. 6078. Springer, 259--370. Google ScholarDigital Library
- Reinhard Bauer, Tobias Columbus, Ignaz Rutter, and Dorothea Wagner. 2013. Search-space size in contraction hierarchies In Automata, Languages, and Programming. Lecture Notes in Computer Science, Vol. 7965. Springer, 93--104. Google ScholarDigital Library
- Reinhard Bauer, Gianlorenzo D'Angelo, Daniel Delling, Andrea Schumm, and Dorothea Wagner. 2012. The shortcut problem—complexity and algorithms. Journal of Graph Algorithms and Applications 16, 2, 447--481. http://jgaa.info/16/270.html.Google ScholarCross Ref
- Hans L. Bodlaender. 1993. A tourist guide through treewidth. Acta Cybernetica 11, 1--21.Google Scholar
- Hans L. Bodlaender. 2007. Treewidth: Structure and algorithms. In Structural Information and Communication Complexity. Lecture Notes in Computer Science, Vol. 4474. Spriniger, 11--25. Google ScholarDigital Library
- Hans L. Bodlaender and Arie M. C. A. Koster. 2010. Treewidth computations I. upper bounds. Information and Computation 208, 3, 259--275. Google ScholarDigital Library
- Soma Chaudhuri and Christos Zaroliagis. 2000. Shortest paths in digraphs of small treewidth. Part I: Sequential algorithms. Algorithmica 27, 3, 212--226.Google ScholarCross Ref
- Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck. 2013. PHAST: Hardware-accelerated shortest path trees. Journal of Parallel and Distributed Computing 73, 7, 940--952. http://www.sciencedirect.com/science/article/pii/S074373151200041X.Google ScholarCross Ref
- Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. 2011a. Customizable route planning. In Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11). 376--387. Google ScholarDigital Library
- Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. 2014. Robust distance queries on massive networks. In Algorithms—ESA 2014. Lecture Notes in Computer Science, Vol. 8737. Springer, 321--333.Google Scholar
- Daniel Delling, Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck. 2015. Customizable route planning in road networks. Transportation Science. Published online May 22, 2015. http://dx.doi.org/10.1287/trsc.2014.0579.Google Scholar
- Daniel Delling, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck. 2011b. Graph partitioning with natural cuts. In Proceedings of the 25th International Parallel and Distributed Processing Symposium (IPDPS'11). IEEE, Los Alamitos, CA, 1135--1146. Google ScholarDigital Library
- Daniel Delling, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck. 2012. Exact combinatorial branch-and-bound for graph bisection. In Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12). 30--44. Google ScholarDigital Library
- Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. 2011c. Faster batched shortest paths in road networks. In Proceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'11). 52--63.Google Scholar
- Daniel Delling and Renato F. Werneck. 2013. Faster customization of road networks. In Experimental Algorithms. Lecture Notes in Computer Science, Vol. 7933. Springer, 30--42.Google Scholar
- Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson (Eds.). 2009. The Shortest Path Problem: Ninth DIMACS Implementation Challenge. DIMACS Book, Vol. 74. American Mathematical Society.Google Scholar
- Edsger W. Dijkstra. 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1, 269--271. Google ScholarDigital Library
- D. R. Fulkerson and O. A. Gross. 1965. Incidence matrices and interval graphs. Pacific Journal of Mathematics 15, 3, 835--855.Google ScholarCross Ref
- Robert Geisberger, Dennis Luxen, Peter Sanders, Sabine Neubauer, and Lars Volker. 2010. Fast detour computation for ride sharing. In Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'10). 88--99.Google Scholar
- Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. 2008. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Experimental Algorithms. Lecture Notes in Computer Science, Vol. 5038. Springer, 319--333. Google ScholarDigital Library
- Robert Geisberger, Peter Sanders, Dominik Schultes, and Christian Vetter. 2012. Exact routing in large road networks using contraction hierarchies. Transportation Science 46, 3, 388--404. Google ScholarDigital Library
- Alan George. 1973. Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis 10, 2, 345--363.Google ScholarDigital Library
- Alan George and Joseph W. Liu. 1978. A quotient graph model for symmetric factorization. In Sparse Matrix Proceedings, I. S. Duff and G. W. Stewart (Eds.). SIAM, Philadelphia, PA, 154--175.Google Scholar
- Alan George and Joseph W. Liu. 1989. The evolution of the minimum degree ordering algorithm. SIAM Review 31, 1, 1--19. Google ScholarDigital Library
- John R. Gilbert and Robert Tarjan. 1986. The analysis of a nested dissection algorithm. Numerische Mathematik 50, 4, 377--404. Google ScholarDigital Library
- Michael Hamann and Ben Strasser. 2015. Graph Bisection with Pareto-Optimization. Technical Report. arXiv:1504.03812. http://arxiv.org/abs/1504.03812.Google Scholar
- Martin Holzer, Frank Schulz, and Dorothea Wagner. 2008. Engineering multilevel overlay graphs for shortest-path queries. ACM Journal of Experimental Algorithmics 13, Article No. 5. Google ScholarDigital Library
- Haim Kaplan, Ron Shamir, and Robert Tarjan. 1999. Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM Journal on Computing 28, 5, 1906--1922. Google ScholarDigital Library
- George Karypis and Vipin Kumar. 1999. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing 20, 1, 359--392. http://dx.doi.org/10.1137/S1064827595287997. Google ScholarDigital Library
- Sebastian Knopp, Peter Sanders, Dominik Schultes, Frank Schulz, and Dorothea Wagner. 2007. Computing many-to-many shortest paths using highway hierarchies. In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX'07). 36--45. Google ScholarDigital Library
- Moritz Kobitzsch, Marcel Radermacher, and Dennis Schieferdecker. 2013. Evolution and evaluation of the penalty method for alternative graphs. In Proceedings of the 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'13). 94--107. http://drops.dagstuhl.de/opus/volltexte/2013/4247.Google Scholar
- Richard J. Lipton, Donald J. Rose, and Robert Tarjan. 1979. Generalized nested dissection. SIAM Journal on Numerical Analysis 16, 2, 346--358.Google ScholarCross Ref
- Catherine C. McGeoch, Peter Sanders, Rudolf Fleischer, Paul R. Cohen, and Doina Precup. 2002. Using finite experiments to study asymptotic performance. In Experimental Algorithmics—From Algorithm Design to Robust and Efficient Software. Lecture Notes in Computer Science, Vol. 2547. Springer, 93--126. http://dx.doi.org/10.1007/3-540-36383-1_5. Google ScholarDigital Library
- Nikola Milosavljević. 2012. On optimal preprocessing for contraction hierarchies. In Proceedings of the 5th ACM SIGSPATIAL International Workshop on Computational Transportation Science. ACM, New York, NY, 33--38. Google ScholarDigital Library
- Léon Planken, Mathijs de Weerdt, and Roman van Krogt. 2012. Computing all-pairs shortest paths by leveraging low treewidth. Journal of Artificial Intelligence Research 43, 1, 353--388. Google ScholarDigital Library
- Alex Pothen. 1988. The Complexity of Optimal Elimination Trees. Technical Report. Pennsylvania State University.Google Scholar
- Michael Rice and Vassilis Tsotras. 2010. Graph indexing of road networks for shortest path queries with label restrictions. Proceedings of the VLDB Endowment 4, 2, 69--80. Google ScholarDigital Library
- Peter Sanders and Dominik Schultes. 2012. Engineering highway hierarchies. ACM Journal of Experimental Algorithmics 17, 1, 1--40. Google ScholarDigital Library
- Peter Sanders and Christian Schulz. 2013. Think locally, act globally: Highly balanced graph partitioning. In Experimental Algorithms. Lecture Notes in Computer Science, Vol. 7933. Springer, 164--175.Google Scholar
- Aaron Schild and Christian Sommer. 2015. On balanced separators in road networks. In Experimental Algorithms. Lecture Notes in Computer Science, Vol. 9125. Springer, 286--297. Google ScholarDigital Library
- Frank Schulz, Dorothea Wagner, and Karsten Weihe. 2000. Dijkstra's algorithm on-line: An empirical case study from public railroad transport. ACM Journal of Experimental Algorithmics 5, 12, 1--23. Google ScholarDigital Library
- Sabine Storandt. 2013. Contraction hierarchies on grid graphs. In KI 2013: Advances in Artificial Intelligence. Lecture Notes in Computer Science, Vol. 8077. Springer, 236--247.Google Scholar
- Nathan Sturtevant. 2012. Benchmarks for grid-based pathfinding. Transactions on Computational Intelligence and AI in Games 4, 2, 144--148.Google ScholarCross Ref
- William F. Tinney and J. W. Walker. 1967. Direct solutions of sparse network equations by optimally ordered triangular factorization. Proceedings of the IEEE 55, 11, 1801--1809.Google ScholarCross Ref
- Michael Wegner. 2014. Finding Small Node Separators. Bachelor's Thesis. Karlsruhe Institute of Technology.Google Scholar
- Fang Wei. 2010. TEDI: Efficient shortest path query answering on graphs. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data (SIGMOD'10). ACM, New York, NY. Google ScholarDigital Library
- Mihalis Yannakakis. 1981. Computing the minimum fill-in is NP-complete. SIAM Journal on Algebraic and Discrete Methods 2, 1, 77--79.Google ScholarCross Ref
- Tim Zeitz. 2013. Weak Contraction Hierarchies Work! Bachelor's Thesis. Karlsruhe Institute of Technology.Google Scholar
Index Terms
- Customizable Contraction Hierarchies
Recommendations
On optimal preprocessing for contraction hierarchies
IWCTS '12: Proceedings of the 5th ACM SIGSPATIAL International Workshop on Computational Transportation ScienceFor some graph classes, most notably real-world road networks, shortest path queries can be answered very efficiently if the graph is preprocessed into a contraction hierarchy. The preprocessing algorithm contracts nodes in some order, adding new edges (...
Customizable Contraction Hierarchies
Proceedings of the 13th International Symposium on Experimental Algorithms - Volume 8504We consider the problem of quickly computing shortest paths in weighted graphs given auxiliary data derived in an expensive preprocessing phase. By adding a fast weight-customization phase, we extend Contraction Hierarchies [12] to support the three-...
Subgraph induced by the set of degree 5 vertices in a contraction critically 5-connected graph
An edge of a 5-connected graph is said to be contractible if the contraction of the edge results in a 5-connected graph. A 5-connected graph with no contractible edge is said to be contraction critically 5-connected. Let G be a contraction critically 5-...
Comments