{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T03:35:05Z","timestamp":1769312105371,"version":"3.49.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2007,2,9]],"date-time":"2007-02-09T00:00:00Z","timestamp":1170979200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2007,2,9]]},"abstract":"<jats:p>\n            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\n            <jats:italic>arc-flag approach<\/jats:italic>\n            and is based on Dijkstra's algorithm. In the arc-flag approach, we allow a preprocessing of the network data to generate additional information, which is then used to speedup shortest-path queries. In the preprocessing phase, the graph is divided into regions and information is gathered on whether an arc is on a shortest path into a given region. The arc-flag method combined with an appropriate partitioning and a bidirected search achieves an average speedup factor of more than 500 compared to the standard algorithm of Dijkstra on large networks (1 million nodes, 2.5 million arcs). This combination narrows down the search space of Dijkstra's algorithm to almost the size of the corresponding shortest path for long-distance shortest-path queries. We conduct an experimental study that evaluates which partitionings are best suited for the arc-flag method. In particular, we examine partitioning algorithms from computational geometry and a multiway arc separator partitioning. The evaluation was done on German road networks. The impact of different partitions on the speedup of the shortest path algorithm are compared. Furthermore, we present an extension of the speedup technique to multiple levels of partitions. With this multilevel variant, the same speedup factors can be achieved with smaller space requirements. It can, therefore, be seen as a compression of the precomputed data that preserves the correctness of the computed shortest paths.\n          <\/jats:p>","DOI":"10.1145\/1187436.1216585","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":48,"title":["Partitioning graphs to speedup Dijkstra's algorithm"],"prefix":"10.1145","volume":"11","author":[{"given":"Rolf H.","family":"M\u00f6hring","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany"}]},{"given":"Heiko","family":"Schilling","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany"}]},{"given":"Birk","family":"Sch\u00fctz","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Karlsruhe (TH), Karlsruhe, Germany"}]},{"given":"Dorothea","family":"Wagner","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Karlsruhe (TH), Karlsruhe, Germany"}]},{"given":"Thomas","family":"Willhalm","sequence":"additional","affiliation":[{"name":"Universit\u00e4t Karlsruhe (TH), Karlsruhe, Germany"}]}],"member":"320","published-online":{"date-parts":[[2007,2,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.277767"},{"key":"e_1_2_1_2_1","volume-title":"Eds","author":"Battista G. D.","year":"2003","unstructured":"Battista , G. D. and Zwick , U. , Eds . 2003 . Algorithms - ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings. Lecture Notes in Computer Science, vol. 2832 . Springer , New York. Battista, G. D. and Zwick, U., Eds. 2003. Algorithms - ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings. Lecture Notes in Computer Science, vol. 2832. Springer, New York."},{"key":"e_1_2_1_3_1","volume-title":"IGIS '94: Geographic Information Systems, International Workshop on Advanced Information Systems, J, Nievergelt, T. Roos, H.-J. Schek, and P. Widmayer, Eds. Lecture Notes in Computer Science","volume":"884","author":"Car A.","unstructured":"Car , A. and Frank , A. U . 1994. Modelling a hierarchy of space applied to large road networks . In IGIS '94: Geographic Information Systems, International Workshop on Advanced Information Systems, J, Nievergelt, T. Roos, H.-J. Schek, and P. Widmayer, Eds. Lecture Notes in Computer Science , vol. 884 . Springer, Heidelberg, 15--24. Car, A. and Frank, A. U. 1994. Modelling a hierarchy of space applied to large road networks. In IGIS '94: Geographic Information Systems, International Workshop on Advanced Information Systems, J, Nievergelt, T. Roos, H.-J. Schek, and P. Widmayer, Eds. Lecture Notes in Computer Science, vol. 884. Springer, Heidelberg, 15--24."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.10.2.163"},{"key":"e_1_2_1_5_1","unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms. The MIT Press Cambridge MA.   Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms. The MIT Press Cambridge MA."},{"key":"e_1_2_1_6_1","volume-title":"Numerische Mathematik.","author":"Dijkstra E. W.","unstructured":"Dijkstra , E. W. 1959. A note on two problems in connexion with graphs . In Numerische Mathematik. Vol. 1 . Mathematisch Centrum, Amsterdam, The Netherlands , 269--271. Dijkstra, E. W. 1959. A note on two problems in connexion with graphs. In Numerische Mathematik. Vol. 1. Mathematisch Centrum, Amsterdam, The Netherlands, 269--271."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216064"},{"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 Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, A. Buchsbaum, Ed. SIAM","author":"Goldberg A. V.","unstructured":"Goldberg , A. V. and Harrelson , C . 2005. Computing the shortest path: A&ast; search meets graph theory . In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, A. Buchsbaum, Ed. SIAM , Philadelphia, PA, USA, 156--165. Goldberg, A. V. and Harrelson, C. 2005. Computing the shortest path: A&ast; search meets graph theory. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, A. Buchsbaum, Ed. SIAM, Philadelphia, PA, USA, 156--165."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics, L. Arge, G. F. Italiano, and R. Sedgewick, Eds. SIAM","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 Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics, L. Arge, G. F. Italiano, and R. Sedgewick, Eds. SIAM , Philadelphia, PA, USA, 100--111. Gutman, R. J. 2004. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics, L. Arge, G. F. Italiano, and R. Sedgewick, Eds. SIAM, Philadelphia, PA, USA, 100--111."},{"key":"e_1_2_1_11_1","volume-title":"Dept. of Informatics","author":"Holzer M.","unstructured":"Holzer , M. 2003. Hierarchical speedup techniques for shortest path algorithms. Tech. rep ., Dept. of Informatics , University of Konstanz , Germany. Holzer, M. 2003. Hierarchical speedup techniques for shortest path algorithms. Tech. rep., Dept. of Informatics, University of Konstanz, Germany."},{"key":"e_1_2_1_12_1","volume-title":"Third International Workshop, C. C. Ribeiro and S. L. Martins, Eds. Lecture Notes in Computer Science","volume":"3059","author":"Holzer M.","unstructured":"Holzer , M. , Schulz , F. , and Willhalm , T . 2004. Combining speedup techniques for shortest-path computations. In Experimental and Efficient Algorithms , Third International Workshop, C. C. Ribeiro and S. L. Martins, Eds. Lecture Notes in Computer Science , vol. 3059 . Springer, Heidelberg, 269--284.) Holzer, M., Schulz, F., and Willhalm, T. 2004. Combining speedup techniques for shortest-path computations. In Experimental and Efficient Algorithms, Third International Workshop, C. C. Ribeiro and S. L. Martins, Eds. Lecture Notes in Computer Science, vol. 3059. Springer, Heidelberg, 269--284.)"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/321992.321993"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the Twelfth International Conference on Data Engineering, S. Y. W. Su, Ed. IEEE Computer Society","author":"Jung S.","unstructured":"Jung , S. and Pramanik , S . 1996. Hiti graph model of topographical roadmaps in navigation systems . In Proceedings of the Twelfth International Conference on Data Engineering, S. Y. W. Su, Ed. IEEE Computer Society , Tokyo, 76--84. Jung, S. and Pramanik, S. 1996. Hiti graph model of topographical roadmaps in navigation systems. In Proceedings of the Twelfth International Conference on Data Engineering, S. Y. W. Su, Ed. IEEE Computer Society, Tokyo, 76--84."},{"key":"e_1_2_1_15_1","volume-title":"METIS: Family of multilevel partitioning algorithms","author":"Karypis G.","year":"1995","unstructured":"Karypis , G. 1995 . METIS: Family of multilevel partitioning algorithms . http:\/\/www-users.cs.umn.edu\/~karypis\/metis\/. Karypis, G. 1995. METIS: Family of multilevel partitioning algorithms. http:\/\/www-users.cs.umn.edu\/~karypis\/metis\/."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595287997"},{"key":"e_1_2_1_17_1","volume-title":"4th InternationalWorkshop, WEA","volume":"3503","author":"K\u00f6hler E.","year":"2005","unstructured":"K\u00f6hler , E. , M\u00f6hring , R. H. , and Schilling , H . 2005. Acceleration of shortest path and constrained shortest path computation. In Experimental and Efficient Algorithms , 4th InternationalWorkshop, WEA 2005 , S. E. Nikoletseas, Ed. Lecture Notes in Computer Science , vol. 3503 . Springer, Heidelberg, 126--138. 10.1007\/11427186_13 K\u00f6hler, E., M\u00f6hring, R. H., and Schilling, H. 2005. Acceleration of shortest path and constrained shortest path computation. In Experimental and Efficient Algorithms, 4th InternationalWorkshop, WEA 2005, S. E. Nikoletseas, Ed. Lecture Notes in Computer Science, vol. 3503. Springer, Heidelberg, 126--138. 10.1007\/11427186_13"},{"key":"e_1_2_1_18_1","volume-title":"Eds. Proceedings in Informatics","volume":"2","author":"Kranakis E.","unstructured":"Kranakis , E. , Krizanc , D. , and Urrutia , J . 1995. Implicit routing and shortest path information (extended abstract). In SIROCCO, L. M. Kirousis and C. Kaklamanis , Eds. Proceedings in Informatics , vol. 2 . Carleton Scientific, 101--112. Kranakis, E., Krizanc, D., and Urrutia, J. 1995. Implicit routing and shortest path information (extended abstract). In SIROCCO, L. M. Kirousis and C. Kaklamanis, Eds. Proceedings in Informatics, vol. 2. Carleton Scientific, 101--112."},{"key":"e_1_2_1_19_1","unstructured":"Lauther U. 1997. Slow preprocessing of graphs for extremely fast shortest path calculations. Lecture at the Workshop on Computational Integer Programming at ZIB.  Lauther U. 1997. Slow preprocessing of graphs for extremely fast shortest path calculations. Lecture at the Workshop on Computational Integer Programming at ZIB."},{"key":"e_1_2_1_20_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 , M. Raubal, A. Sliwinski, and W. Kuhn, Eds. IfGI prints, vol. 22 . Institut f\u00fcr Geoinformatik, Westf\u00e4lische Wilhelms-Universit\u00e4t, 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, M. Raubal, A. Sliwinski, and W. Kuhn, Eds. IfGI prints, vol. 22. Institut f\u00fcr Geoinformatik, Westf\u00e4lische Wilhelms-Universit\u00e4t, M\u00fcnster, 219--230."},{"key":"e_1_2_1_21_1","unstructured":"Mehlhorn K. and N\u00e4her S. 1999. LEDA A platform for Combinatorial and Geometric Computing. Cambridge University Press Cambridge.   Mehlhorn K. and N\u00e4her S. 1999. LEDA A platform for Combinatorial and Geometric Computing. Cambridge University Press Cambridge."},{"key":"e_1_2_1_22_1","volume-title":"13th Annual European Symposium, G. S. Brodal and S. Leonardi, Eds. Lecture Notes in Computer Science","volume":"3669","author":"Sanders P.","unstructured":"Sanders , P. and Schultes , D . 2005. Highway hierarchies hasten exact shortest path queries. In Algorithms---ESA 2005 , 13th Annual European Symposium, G. S. Brodal and S. Leonardi, Eds. Lecture Notes in Computer Science , vol. 3669 . Springer, 568--579. 10.1007\/11561071_51 Sanders, P. and Schultes, D. 2005. Highway hierarchies hasten exact shortest path queries. In Algorithms---ESA 2005, 13th Annual European Symposium, G. S. Brodal and S. Leonardi, Eds. Lecture Notes in Computer Science, vol. 3669. Springer, 568--579. 10.1007\/11561071_51"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/351827.384254"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Wagner D. and Willhalm T. 2003. Geometric speedup techniques for finding shortest paths in large sparse graphs. (See Battista and Zwick {2003} 776--787.)  Wagner D. and Willhalm T. 2003. Geometric speedup techniques for finding shortest paths in large sparse graphs. (See Battista and Zwick {2003} 776--787.)","DOI":"10.1007\/978-3-540-39658-1_69"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics, C. Demetrescu, R. Sedgewick, and R. Tamassia, Eds. SIAM","author":"Wagner D.","unstructured":"Wagner , D. and Willhalm , T . 2005. Drawing graphs to speed up shortest-path computations . In Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics, C. Demetrescu, R. Sedgewick, and R. Tamassia, Eds. SIAM , Philadelphia, PA, USA, 17--25. Wagner, D. and Willhalm, T. 2005. Drawing graphs to speed up shortest-path computations. In Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics, C. Demetrescu, R. Sedgewick, and R. Tamassia, Eds. SIAM, Philadelphia, PA, USA, 17--25."},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Wagner D. Willhalm T. and Zaroliagis C. 2005. Geometric containers for efficient shortest path computation. ACM Journal of Experimental Algorithms 10. 10.1145\/1064546.1103378   Wagner D. Willhalm T. and Zaroliagis C. 2005. Geometric containers for efficient shortest path computation. ACM Journal of Experimental Algorithms 10. 10.1145\/1064546.1103378","DOI":"10.1145\/1064546.1103378"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1187436.1216585","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1187436.1216585","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:08:11Z","timestamp":1750262891000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1187436.1216585"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,2,9]]},"references-count":26,"alternative-id":["10.1145\/1187436.1216585"],"URL":"https:\/\/doi.org\/10.1145\/1187436.1216585","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,2,9]]}}}