Nikola Milosavljević
ABSTRACT
For 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 (shortcuts) in the process. While preprocessing and query algorithm work for any contraction ordering, it is desirable to use one that produces as few shortcuts as possible.
It is known that the problem of minimizing the size (number of edges) of a given graph's contraction hierarchy is APX-hard. Also, any graph can be processed into a contraction hierarchy with at most O(nh log D) edges, where n, D, and h are the number of nodes, the diameter, and the highway dimension of the original graph, respectively.
In this paper we show that the O(nh log D) bound is tight for a wide range of parameters n, D, and h. We also show that planar graphs, despite having highway dimension Ω(√n), can be preprocessed into a graph of size O(n log n). Finally, we present a simpler proof of APX-hardness.
- I. Abraham, D. Delling, A. Fiat, A. V. Goldberg, and R. F. Werneck. VC-dimension and shortest path algorithms. In Proceedings of the 38th international colloquim conference on Automata, languages and programming - Volume Part I, ICALP'11, pages 690--699, Berlin, Heidelberg, 2011. Springer-Verlag. Google Scholar
Digital Library
- I. Abraham, A. Fiat, A. V. Goldberg, and R. F. Werneck. Highway dimension, shortest paths, and provably efficient algorithms. In M. Charikar, editor, SODA, pages 782--793. SIAM, 2010. Google ScholarDigital Library
- R. Bauer, T. Columbus, B. Katz, M. Krug, and D. Wagner. Preprocessing speed-up techniques is hard. In Proceedings of the 7th international conference on Algorithms and Complexity, CIAC'10, pages 359--370, Berlin, Heidelberg, 2010. Springer-Verlag. Google ScholarDigital Library
- I. Dinur and S. Safra. On the hardness of approximating minimum vertex cover. Annals of Mathematics, 162(1):439--485, 2005. Google ScholarDigital Library
- D. Eppstein and M. T. Goodrich. Studying (non-planar) road networks through an algorithmic lens. In Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, GIS '08, pages 16:1--16:10, New York, NY, USA, 2008. ACM. Google ScholarDigital Library
- R. Geisberger, P. Sanders, D. Schultes, and C. Vetter. Exact routing in large road networks using contraction hierarchies. Transportation Science, 2012. Google ScholarDigital Library
- R. J. Lipton, D. J. Rose, and R. E. Tarjan. Generalized nested dissection. SIAM J. Numer. Anal., 16(2):346--358, 1979.Google ScholarDigital Library
Index Terms
- On optimal preprocessing for contraction hierarchies
Recommendations
Search-space size in contraction hierarchies
Contraction hierarchies are a speed-up technique to improve the performance of shortest-path computations, which works very well in practice. Despite convincing practical results, there is still a lack of theoretical explanation for this behavior.In ...
Complexity and approximation of the Constrained Forest problem
Given an undirected graph on n vertices with weights on its edges, Min WCF (p) consists of computing a covering forest of minimum weight such that each of its tree components contains at least p vertices. It has been proved that Min WCF (p) is NP-hard ...
A faster algorithm for computing the girth of planar and bounded genus graphs
The girth of a graph G is the length of a shortest cycle of G. In this article we design an O(n5/4 log n) algorithm for finding the girth of an undirected n-vertex planar graph, the first o(n2) algorithm for this problem. We also extend our results for ...
Comments