{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,9]],"date-time":"2024-07-09T05:15:29Z","timestamp":1720502129917},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2005,12,31]]},"abstract":"<jats:p>\n            In practice, computing a shortest path from one node to another in a directed graph is a very common task. This problem is classically solved by Dijkstra's algorithm. Many techniques are known to speed up this algorithm heuristically, while optimality of the solution can still be guaranteed. In most studies, such techniques are considered individually. The focus of our work is\n            <jats:italic>combination<\/jats:italic>\n            of speed-up techniques for Dijkstra's algorithm. We consider all possible combinations of four known techniques, namely,\n            <jats:italic>goal-directed search<\/jats:italic>\n            ,\n            <jats:italic>bidirectional search<\/jats:italic>\n            ,\n            <jats:italic>multilevel approach<\/jats:italic>\n            , and\n            <jats:italic>shortest-path containers<\/jats:italic>\n            , and show how these can be implemented. In an extensive experimental study, we compare the performance of the various combinations and analyze how the techniques harmonize when jointly applied. Several real-world graphs from road maps and public transport and three types of generated random graphs are taken into account.\n          <\/jats:p>","DOI":"10.1145\/1064546.1180616","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":23,"title":["Combining speed-up techniques for shortest-path computations"],"prefix":"10.1145","volume":"10","author":[{"given":"Martin","family":"Holzer","sequence":"first","affiliation":[{"name":"Universit\u00e4t Karlsruhe, Karlsruhe, Germany"}]},{"given":"Frank","family":"Schulz","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Karlsruhe, Karlsruhe, Germany"}]},{"given":"Dorothea","family":"Wagner","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Karlsruhe, Karlsruhe, Germany"}]},{"given":"Thomas","family":"Willhalm","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Karlsruhe, Karlsruhe, Germany"}]}],"member":"320","published-online":{"date-parts":[[2005,12,31]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Ahuja R. Magnanti T. and Orlin J. 1993. Network flows. Prentice--Hall Englewood Cliffs NJ.]]  Ahuja R. Magnanti T. and Orlin J. 1993. Network flows. Prentice--Hall Englewood Cliffs NJ.]]"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798337716"},{"key":"e_1_2_1_3_1","volume-title":"Proc. 10th European Symposium on Algorithms (ESA). LNCS","volume":"2461","author":"Barrett C.","unstructured":"Barrett , C. , Bisset , K. , Jacob , R. , Konjevod , G. , and Marathe , M . 2002. Classical and contemporary shortest path problems in road networks: Implementation and experimental analysis of the TRANSIMS router . In Proc. 10th European Symposium on Algorithms (ESA). LNCS , vol. 2461 . Springer-Verlag, New York. 126--128.]] Barrett, C., Bisset, K., Jacob, R., Konjevod, G., and Marathe, M. 2002. Classical and contemporary shortest path problems in road networks: Implementation and experimental analysis of the TRANSIMS router. In Proc. 10th European Symposium on Algorithms (ESA). LNCS, vol. 2461. Springer-Verlag, New York. 126--128.]]"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3226663.3227073"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/363269.363610"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA","author":"Goldberg A.","year":"2005","unstructured":"Goldberg , A. and Harrelson , C . 2005. Computing the shortest path: A&ast; search meets graph theory . In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005 ). SIAM.]] Goldberg, A. and Harrelson, C. 2005. Computing the shortest path: A&ast; search meets graph theory. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005). SIAM.]]"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX 06)","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 (ALENEX 06) . 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 (ALENEX 06). SIAM. 129--143.]]"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45678-3_43"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/647911.740638"},{"key":"e_1_2_1_13_1","volume-title":"Proc. 6th Workshop on Algorithm Engineering and Experiments (ALENEX), SIAM, 100--111","author":"Gutman R. J.","year":"2004","unstructured":"Gutman , R. J. 2004 . Reach-based routing: A new approach to shortest path algorithms optimized for road networks . In Proc. 6th Workshop on Algorithm Engineering and Experiments (ALENEX), SIAM, 100--111 .]] Gutman, R. J. 2004. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In Proc. 6th Workshop on Algorithm Engineering and Experiments (ALENEX), SIAM, 100--111.]]"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_2_1_15_1","volume-title":"Dept. of Informatics","author":"Holzer M.","year":"2003","unstructured":"Holzer , M. 2003. Hierarchical speed-up techniques for shortest-path algorithms. Tech. rep ., Dept. of Informatics , University of Konstanz , Germany. http:\/\/www.ub.uni-konstanz.de\/kops\/volltexte\/ 2003 \/1038\/.]] Holzer, M. 2003. Hierarchical speed-up techniques for shortest-path algorithms. Tech. rep., Dept. of Informatics, University of Konstanz, Germany. http:\/\/www.ub.uni-konstanz.de\/kops\/volltexte\/2003\/1038\/.]]"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX 06)","author":"Holzer M.","unstructured":"Holzer , M. , Schulz , F. , and Wagner , D . 2006. Engineering multilevel overlay graphs for shortest-path queries . In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX 06) . SIAM. 156--170.]] Holzer, M., Schulz, F., and Wagner, D. 2006. Engineering multilevel overlay graphs for shortest-path queries. In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX 06). SIAM. 156--170.]]"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.687976"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2002.1033772"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622776.1622787"},{"key":"e_1_2_1_20_1","unstructured":"K\u00f6hler E. M\u00f6hring R. H. and Schilling H. 2004. Acceleration of shortest path computation. Article 42 Technische Universit\u00e4t Berlin Fakult\u00e4t II Mathematik und Naturwissenschaften.]]  K\u00f6hler E. M\u00f6hring R. H. and Schilling H. 2004. Acceleration of shortest path computation. Article 42 Technische Universit\u00e4t Berlin Fakult\u00e4t II Mathematik und Naturwissenschaften.]]"},{"key":"e_1_2_1_21_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_22_1","volume-title":"Proc. 12th Symp. on Discrete Algorithms. 797--806","author":"Meyer U.","year":"2001","unstructured":"Meyer , U. 2001 . Single-source shortest-paths on arbitrary directed graphs in linear average-case time . In Proc. 12th Symp. on Discrete Algorithms. 797--806 .]] Meyer, U. 2001. Single-source shortest-paths on arbitrary directed graphs in linear average-case time. In Proc. 12th Symp. on Discrete Algorithms. 797--806.]]"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)E0349-G"},{"key":"e_1_2_1_24_1","unstructured":"N\u00e4her S. and Mehlhorn K. 1999. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press. (http:\/\/www.algorithmic-solutions.com).]]   N\u00e4her S. and Mehlhorn K. 1999. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press. (http:\/\/www.algorithmic-solutions.com).]]"},{"key":"e_1_2_1_25_1","volume-title":"Proc. Algorithm Engineering and Experiments (ALENEX), LNCS","volume":"2409","author":"Pettie S.","unstructured":"Pettie , S. , Ramachandran , V. , and Sridhar , S . 2002. Experimental evaluation of a new shortest path algorithm . In Proc. Algorithm Engineering and Experiments (ALENEX), LNCS , vol. 2409 . Springer-Verlag, New York. 124--142.]] Pettie, S., Ramachandran, V., and Sridhar, S. 2002. Experimental evaluation of a new shortest path algorithm. In Proc. Algorithm Engineering and Experiments (ALENEX), LNCS, vol. 2409. Springer-Verlag, New York. 124--142.]]"},{"key":"e_1_2_1_27_1","volume-title":"Proc. 6th Int. Conf. Appl. Computer Networking in Architecture, Construction, Design, Civil Eng., and Urban Planning (europIA '97)","author":"Preuss T.","unstructured":"Preuss , T. and Syrbe , J . -H. 1997. An integrated traffic information system . In Proc. 6th Int. Conf. Appl. Computer Networking in Architecture, Construction, Design, Civil Eng., and Urban Planning (europIA '97) .]] Preuss, T. and Syrbe, J.-H. 1997. An integrated traffic information system. In Proc. 6th Int. Conf. Appl. Computer Networking in Architecture, Construction, Design, Civil Eng., and Urban Planning (europIA '97).]]"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_51"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/351827.384254"},{"key":"e_1_2_1_30_1","volume-title":"Proc. 4th Workshop on Algorithm Engineering and Experiments (ALENEX). 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 Proc. 4th Workshop on Algorithm Engineering and Experiments (ALENEX). LNCS , vol. 2409 . Springer-Verlag, New York. 43--59.]] Schulz, F., Wagner, D., and Zaroliagis, C. 2002. Using multi-level graphs for timetable information in railway systems. In Proc. 4th Workshop on Algorithm Engineering and Experiments (ALENEX). LNCS, vol. 2409. Springer-Verlag, New York. 43--59.]]"},{"key":"e_1_2_1_31_1","volume-title":"Proc. Symp. on Large Spatial Databases. 94--111","author":"Shekhar S.","unstructured":"Shekhar , S. , Fetterer , A. , and Goyal , B . 1997. Materialization trade-offs in hierarchical shortest path algorithms . In Proc. Symp. on Large Spatial Databases. 94--111 .]] Shekhar, S., Fetterer, A., and Goyal, B. 1997. Materialization trade-offs in hierarchical shortest path algorithms. In Proc. Symp. on Large Spatial Databases. 94--111.]]"},{"key":"e_1_2_1_32_1","volume-title":"Proc. 9th IEEE Int. Conf. Data Eng. 31--39","author":"Shekhar S.","unstructured":"Shekhar , S. , Kohli , A. , and Coyle , M . 1993. Path computation algorithms for advanced traveler information system (ATIS) . In Proc. 9th IEEE Int. Conf. Data Eng. 31--39 .]] Shekhar, S., Kohli, A., and Coyle, M. 1993. Path computation algorithms for advanced traveler information system (ATIS). In Proc. 9th IEEE Int. Conf. Data Eng. 31--39.]]"},{"key":"e_1_2_1_33_1","volume-title":"Proc. 11th European Symposium on Algorithms (ESA), 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 Proc. 11th European Symposium on Algorithms (ESA), LNCS , vol. 2832 . Springer-Verlag, New York. 776--787.]] Wagner, D. and Willhalm, T. 2003. Geometric speed-up techniques for finding shortest paths in large sparse graphs. In Proc. 11th European Symposium on Algorithms (ESA), LNCS, vol. 2832. Springer-Verlag, New York. 776--787.]]"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/49.12889"},{"key":"e_1_2_1_36_1","unstructured":"Willhalm T. and Wagner D. 2006. Shortest path speedup techniques. In Algorithmic Methods for Railway Optimization. LNCS. Springer-Verlag New York. To appear.]]  Willhalm T. and Wagner D. 2006. Shortest path speedup techniques. In Algorithmic Methods for Railway Optimization. LNCS. Springer-Verlag New York. To appear.]]"},{"key":"e_1_2_1_37_1","first-page":"2","article-title":"A comparison between label-setting and label-correcting algorithms for computing one-to-one shortest paths","volume":"4","author":"Zhan F. B.","year":"2000","unstructured":"Zhan , F. B. and Noon , C. E. 2000 . A comparison between label-setting and label-correcting algorithms for computing one-to-one shortest paths . Journal of Geographic Information and Decision Analysis 4 , 2 .]] Zhan, F. B. and Noon, C. E. 2000. A comparison between label-setting and label-correcting algorithms for computing one-to-one shortest paths. Journal of Geographic Information and Decision Analysis 4, 2.]]","journal-title":"Journal of Geographic Information and Decision Analysis"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/647911.740642"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1064546.1180616","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T12:11:40Z","timestamp":1672229500000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1064546.1180616"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12,31]]},"references-count":35,"alternative-id":["10.1145\/1064546.1180616"],"URL":"https:\/\/doi.org\/10.1145\/1064546.1180616","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,12,31]]}}}