{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T21:32:19Z","timestamp":1778535139591,"version":"3.51.4"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2009,2,1]],"date-time":"2009-02-01T00:00:00Z","timestamp":1233446400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["WA 654\/16-1"],"award-info":[{"award-number":["WA 654\/16-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["FP6-021235-2"],"award-info":[{"award-number":["FP6-021235-2"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2009,2]]},"abstract":"<jats:p>\n            An overlay graph of a given graph\n            <jats:italic>G<\/jats:italic>\n            = (\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ) on a subset\n            <jats:italic>S<\/jats:italic>\n            \u2286\n            <jats:italic>V<\/jats:italic>\n            is a graph with vertex set\n            <jats:italic>S<\/jats:italic>\n            and edges corresponding to shortest paths in\n            <jats:italic>G<\/jats:italic>\n            . 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\n            <jats:italic>S<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.1145\/1412228.1412239","type":"journal-article","created":{"date-parts":[[2008,10,7]],"date-time":"2008-10-07T12:48:29Z","timestamp":1223383709000},"source":"Crossref","is-referenced-by-count":32,"title":["Engineering multilevel overlay graphs for shortest-path queries"],"prefix":"10.1145","volume":"13","author":[{"given":"Martin","family":"Holzer","sequence":"first","affiliation":[{"name":"KIT, Universit\u00e4t Karlsruhe (TH), Karlsruhe, Germany"}]},{"given":"Frank","family":"Schulz","sequence":"additional","affiliation":[{"name":"KIT, Universit\u00e4t Karlsruhe (TH), Karlsruhe, Germany"}]},{"given":"Dorothea","family":"Wagner","sequence":"additional","affiliation":[{"name":"KIT, Universit\u00e4t Karlsruhe (TH), Karlsruhe, Germany"}]}],"member":"320","published-online":{"date-parts":[[2009,2,23]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuja R. K.","year":"1993","unstructured":"Ahuja , R. K. , Magnanti , T. L. , and Orlin , J. B . 1993 . Network Flows: Theory, Algorithms, and Applications . Prentice Hall . Englewood Cliffs, NJ. Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice Hall. Englewood Cliffs, NJ."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 9th Workshop on Algorithm Engineering and Experiments. SIAM. 46--59","author":"Bast H.","unstructured":"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 . 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."},{"key":"e_1_2_1_4_1","volume-title":"Random Graphs","author":"Bollob\u00e1s B.","unstructured":"Bollob\u00e1s , B. 1985. Random Graphs . Academic Press , London . Bollob\u00e1s, B. 1985. Random Graphs. Academic Press, London."},{"key":"e_1_2_1_5_1","unstructured":"Borgi I. Graf J. Holzer M. Schulz F. and Willhalm T. 2005. A graph generator. http:\/\/i11www.ira.uka.de\/resources\/graphgenerator.php.  Borgi I. Graf J. Holzer M. Schulz F. and Willhalm T. 2005. A graph generator. http:\/\/i11www.ira.uka.de\/resources\/graphgenerator.php."},{"key":"e_1_2_1_6_1","volume-title":"Eds","author":"Brandes U.","year":"2005","unstructured":"Brandes , U. and Erlebach , T. , Eds . 2005 . Network Analysis. LNCS, vol. 3418 . Springer , New York. Brandes, U. and Erlebach, T., Eds. 2005. Network Analysis. LNCS, vol. 3418. Springer, New York."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the Workshop on DIMACS Shortest-Path Challenge. To appear. http:\/\/i11www.ira.uka.de\/members\/mholzer\/publications\/pdf\/dhmsw-hpmlg-06","author":"Delling D.","unstructured":"Delling , D. , Holzer , M. , M\u00fcller , 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. Delling, D., Holzer, M., M\u00fcller, 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."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Workshop on DIMACS Shortest-Path Challenge. To appear. http:\/\/i11www.ira.uka.de\/members\/delling\/files\/dssw-hhs-06","author":"Delling D.","unstructured":"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. 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."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 16th Symposium on Discrete Algorithms. SIAM, 156--165","author":"Goldberg A.","unstructured":"Goldberg , A. and Harrelson , C . 2005. Computing the shortest path: A&ast; search meets graph theory . In Proceedings of the 16th Symposium on Discrete Algorithms. SIAM, 156--165 . Goldberg, A. and Harrelson, C. 2005. Computing the shortest path: A&ast; search meets graph theory. In Proceedings of the 16th Symposium on Discrete Algorithms. SIAM, 156--165."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 8th Workshop on Algorithm Engineering and Experiments. SIAM. 129--143","author":"Goldberg A.","unstructured":"Goldberg , A. , Kaplan , H. , and Werneck , R . 2006. Reach for A&ast;: Efficient point-to-point shortest path algorithms . In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments. SIAM. 129--143 . Goldberg, A., Kaplan, H., and Werneck, R. 2006. Reach for A&ast;: Efficient point-to-point shortest path algorithms. In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments. SIAM. 129--143."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 6th Workshop on Algorithm Engineering and Experiments. SIAM. 100--111","author":"Gutman R.","year":"2004","unstructured":"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 . 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."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 3rd Workshop on Experimental and Efficient Algorithms. LNCS","volume":"3059","author":"Holzer M.","unstructured":"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. 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."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_56"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.687976"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2002.1033772"},{"key":"e_1_2_1_18_1","unstructured":"Karypis G. 2005. METIS. http:\/\/www-users.cs.umn.edu\/~karypis\/metis.  Karypis G. 2005. METIS. http:\/\/www-users.cs.umn.edu\/~karypis\/metis."},{"key":"e_1_2_1_19_1","volume-title":"Geoinformation und Mobilit\u00e4t -- von der Forschung zur praktischen Anwendung.","author":"Lauther U.","unstructured":"Lauther , U. 2004. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background . In Geoinformation und Mobilit\u00e4t -- von der Forschung zur praktischen Anwendung. Vol. 22 . IfGI prints, Institut f\u00fcr Geoinformatik, M\u00fcnster . 219--230. Lauther, U. 2004. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background. In Geoinformation und Mobilit\u00e4t -- von der Forschung zur praktischen Anwendung. Vol. 22. IfGI prints, Institut f\u00fcr Geoinformatik, M\u00fcnster. 219--230."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/11427186_18"},{"key":"e_1_2_1_21_1","unstructured":"N\u00e4her S. and Mehlhorn K. 1999. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press Cambridge. http:\/\/www.algorithmic-solutions.com.   N\u00e4her S. and Mehlhorn K. 1999. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press Cambridge. http:\/\/www.algorithmic-solutions.com."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_51"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_71"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 6th Workshop on Experimental and Efficient Algorithms. LNCS","author":"Schultes D.","unstructured":"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. 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."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/351827.384254"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 4th Workshop on Algorithm Engineering and Experiments. LNCS","volume":"2409","author":"Schulz F.","unstructured":"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. 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."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 11th European Symposium on Algorithms. LNCS","volume":"2832","author":"Wagner D.","unstructured":"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. 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."},{"key":"e_1_2_1_29_1","volume-title":"Algorithmic Methods for Railway Optimization. LNCS","volume":"4359","author":"Willhalm T.","unstructured":"Willhalm , T. and Wagner , D . 2007. Shortest path speedup techniques . In Algorithmic Methods for Railway Optimization. LNCS , vol. 4359 . Springer, New York. Willhalm, T. and Wagner, D. 2007. Shortest path speedup techniques. In Algorithmic Methods for Railway Optimization. LNCS, vol. 4359. Springer, New York."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412228.1412239","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1412228.1412239","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:48:51Z","timestamp":1750286931000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412228.1412239"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2]]},"references-count":26,"alternative-id":["10.1145\/1412228.1412239"],"URL":"https:\/\/doi.org\/10.1145\/1412228.1412239","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,2]]}}}