Martin Holzer
Abstract
An overlay graph of a given graph G = (V, E) on a subset S ⊆ V is a graph with vertex set S and edges corresponding to shortest paths in G. In particular, we consider variations of the multilevel overlay graph used in Schulz et al. [2002] to speed up shortest-path computation. In this work, we follow up and present several vertex selection criteria, along with two general strategies of applying these criteria, to determine a subset S of a graph's vertices. The main contribution is a systematic experimental study where we investigate the impact of selection criteria and strategies on multilevel overlay graphs and the resulting speed-up achieved for shortest-path computation: Depending on selection strategy and graph type, a centrality index criterion, selection based on planar separators, and vertex degree turned out to perform best.
- Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice Hall. Englewood Cliffs, NJ. Google Scholar
Digital Library
- Bast, H., Funke, S., Matijevic, D., Sanders, P., and Schultes, D. 2007. Transit to constant shortest-path queries in road networks. In Proceedings of the 9th Workshop on Algorithm Engineering and Experiments. SIAM. 46--59.Google Scholar
- Bauer, R. 2006. Dynamic speed-up techniques for Dijkstra's algorithm. M.S. thesis, Universität Karlsruhe (TH), Fakultät für Informatik. http://i11www.ira.uka.de/teaching/theses/files/da-rbauer-06.pdf.Google Scholar
- Bollobás, B. 1985. Random Graphs. Academic Press, London.Google Scholar
- Borgi, I., Graf, J., Holzer, M., Schulz, F., and Willhalm, T. 2005. A graph generator. http://i11www.ira.uka.de/resources/graphgenerator.php.Google Scholar
- Brandes, U. and Erlebach, T., Eds. 2005. Network Analysis. LNCS, vol. 3418. Springer, New York.Google Scholar
- Delling, D., Holzer, M., Müller, K., Schulz, F., and Wagner, D. 2007a. High-performance multi-level graphs. In Proceedings of the Workshop on DIMACS Shortest-Path Challenge. To appear. http://i11www.ira.uka.de/members/mholzer/publications/pdf/dhmsw-hpmlg-06.pdf.Google Scholar
- Delling, D., Sanders, P., Schultes, D., and Wagner, D. 2007b. Highway hierarchies star. In Proceedings of the Workshop on DIMACS Shortest-Path Challenge. To appear. http://i11www.ira.uka.de/members/delling/files/dssw-hhs-06.pdf.Google Scholar
- Dijkstra, E. W. 1959. A note on two problems in connexion with graphs. Numerische Math. 1, 269--271.Google ScholarDigital Library
- Goldberg, A. and Harrelson, C. 2005. Computing the shortest path: A* search meets graph theory. In Proceedings of the 16th Symposium on Discrete Algorithms. SIAM, 156--165. Google ScholarDigital Library
- Goldberg, A., Kaplan, H., and Werneck, R. 2006. Reach for A*: Efficient point-to-point shortest path algorithms. In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments. SIAM. 129--143.Google Scholar
- Gutman, R. 2004. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In Proceedings of the 6th Workshop on Algorithm Engineering and Experiments. SIAM. 100--111.Google Scholar
- Holzer, M. 2003. Hierarchical speed-up techniques for shortest-path algorithms. M.S. thesis, Universität Konstanz, Fachbereich Informatik und Informationswissenschaft. http://www.ub.uni-konstanz.de/kops/volltexte/2003/1038/.Google Scholar
- Holzer, M., Schulz, F., and Willhalm, T. 2004. Combining speed-up techniques for shortest-path computations. In Proceedings of the 3rd Workshop on Experimental and Efficient Algorithms. LNCS, vol. 3059. Springer, New York. 269--284.Google Scholar
- Holzer, M., Prasinos, G., Schulz, F., Wagner, D., and Zaroliagis, C. 2005. Engineering planar separator algorithms. In Proceedings of the 13th European Symposium on Algorithms. LNCS, vol. 3669. Springer, New York. 628--639. Google ScholarDigital Library
- Jing, N., Huang, Y.-W., and Rundensteiner, E. A. 1998. Hierarchical encoded path views for path query processing: An optimal model and its performance evaluation. IEEE Trans. Knowledge Data Eng. 10, 3. Google ScholarDigital Library
- Jung, S. and Pramanik, S. 2002. An efficient path computation model for hierarchically structured topographical road maps. IEEE Trans. Knowledge Data Eng. 14, 5. Google ScholarDigital Library
- Karypis, G. 2005. METIS. http://www-users.cs.umn.edu/~karypis/metis.Google Scholar
- Lauther, U. 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. IfGI prints, Institut für Geoinformatik, Münster. 219--230.Google Scholar
- Möhring, R. H., Schilling, H., Schütz, B., Wagner, D., and Willhalm, T. 2005. Partitioning graphs to speed up Dijkstra's algorithm. In Proceedings of the 4th Workshop on Experimental and Efficient Algorithms. 189--202. Google ScholarDigital Library
- Näher, S. and Mehlhorn, K. 1999. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press, Cambridge. http://www.algorithmic-solutions.com. Google ScholarDigital Library
- Sanders, P. and Schultes, D. 2005. Highway hierarchies hasten exact shortest path queries. In Proceedings of the 17th European Symposium on Algorithms. Google ScholarDigital Library
- Sanders, P. and Schultes, D. 2006. Engineering highway hierarchies. In Proceedings of the 14th European Symposium on Algorithms. LNCS, vol. 4168. Springer, New York. 804--816. Google ScholarDigital Library
- Schultes, D. and Sanders, P. 2007. Dynamic highway-node routing. In Proceedings of the 6th Workshop on Experimental and Efficient Algorithms. LNCS. Springer, New York. 66--79. Google ScholarDigital Library
- Schulz, F. 2005. Timetable information and shortest paths. Ph.D. thesis, Universität Karlsruhe (TH), Fakultät für Informatik.Google Scholar
- Schulz, F., Wagner, D., and Weihe, K. 2000. Dijkstra's algorithm on-line: An empirical case study from public railroad transport. J. Exp. Algorithmics 5, 12. Google ScholarDigital Library
- Schulz, F., Wagner, D., and Zaroliagis, C. 2002. Using multi-level graphs for timetable information in railway systems. In Proceedings of the 4th Workshop on Algorithm Engineering and Experiments. LNCS, vol. 2409. Springer, New York. 43--59. Google ScholarDigital Library
- Wagner, D. and Willhalm, T. 2003. Geometric speed-up techniques for finding shortest paths in large sparse graphs. In Proceedings of the 11th European Symposium on Algorithms. LNCS, vol. 2832. Springer, New York. 776--787.Google Scholar
- Willhalm, T. and Wagner, D. 2007. Shortest path speedup techniques. In Algorithmic Methods for Railway Optimization. LNCS, vol. 4359. Springer, New York.Google Scholar
Index Terms
- Engineering multilevel overlay graphs for shortest-path queries
Recommendations
Partitioning graphs to speedup Dijkstra's algorithm
We study an acceleration method for point-to-point shortest-path computations in large and sparse directed graphs with given nonnegative arc weights. The acceleration method is called the arc-flag approach and is based on Dijkstra's algorithm. In the ...
Shortest paths in Sierpiński graphs
In 23], Klav ar and Milutinović (1997) proved that there exist at most two different shortest paths between any two vertices in Sierpiński graphs S k n , and showed that the number of shortest paths between any fixed pair of vertices of S k n can be ...
On shortest disjoint paths in planar graphs
For a graph G and a collection of vertex pairs {(s"1,t"1),...,(s"k,t"k)}, the k disjoint paths problem is to find k vertex-disjoint paths P"1,...,P"k, where P"i is a path from s"i to t"i for each i=1,...,k. In the corresponding optimization problem, the ...
Comments