{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T17:40:09Z","timestamp":1778694009760,"version":"3.51.4"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T00:00:00Z","timestamp":1703116800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"French government"},{"name":"National Research Agency","award":["ANR-15-IDEX-01"],"award-info":[{"award-number":["ANR-15-IDEX-01"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>\n            The\n            <jats:italic>k<\/jats:italic>\n            shortest simple path problem (\n            <jats:italic>k<\/jats:italic>\n            SSP) asks to compute a set of top-\n            <jats:italic>k<\/jats:italic>\n            shortest simple paths from a source to a sink in a digraph. Yen (1971) proposed an algorithm with the best-known polynomial time complexity for this problem. Since then, the problem has been widely studied from an algorithm engineering perspective. The most noticeable proposals are the\n            <jats:italic>node-classification<\/jats:italic>\n            (NC) algorithm (Feng, 2014) and the\n            <jats:italic>sidetracks-based<\/jats:italic>\n            (SB) algorithm (Kurz, Mutzel, 2016). The latest offers the best running time at the price of a significant memory consumption.\n          <\/jats:p>\n          <jats:p>\n            We first show how to speed up the SB algorithm using dynamic updates of shortest path trees resulting in a faster algorithm (SB*) with the same memory consumption. We then propose the\n            <jats:italic>parsimonious SB<\/jats:italic>\n            (PSB) algorithm that significantly reduces the memory consumption of SB at the cost of a small increase of the running time. Furthermore, we propose the\n            <jats:italic>postponed node-classification<\/jats:italic>\n            (PNC) algorithm that combines the best of the NC and the SB algorithms. It offers a significant speed up compared to the SB algorithm while using the same amount of memory as the NC algorithm.\n          <\/jats:p>\n          <jats:p>\n            Our experimental results on complex networks show that all the considered algorithms have low memory consumption, and that the PSB algorithm is the fastest. On road networks, the relative performances of the algorithms depend on the number\n            <jats:italic>k<\/jats:italic>\n            of requested paths. Indeed, when the number\n            <jats:italic>k<\/jats:italic>\n            of requested paths is small (i.e.,\n            <jats:italic>k<\/jats:italic>\n            \u2264 20 in our experiments), the SB* algorithm is the fastest among the considered algorithms, but it suffers from a large memory consumption and it offers very bad performances on some queries. When the number of requested paths is large (i.e., larger than 20 according to our experiments), the PNC algorithm is the fastest among the considered algorithms on road networks and it has a low memory footprint. The PNC algorithm is therefore a better choice on road networks.\n          <\/jats:p>","DOI":"10.1145\/3626567","type":"journal-article","created":{"date-parts":[[2023,10,7]],"date-time":"2023-10-07T10:19:22Z","timestamp":1696673962000},"page":"1-23","source":"Crossref","is-referenced-by-count":6,"title":["Finding the\n            <i>k<\/i>\n            Shortest Simple Paths: Time and Space Trade-offs"],"prefix":"10.1145","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4665-4021","authenticated-orcid":false,"given":"Ali","family":"Al Zoobi","sequence":"first","affiliation":[{"name":"Universit\u00e9 C\u00f4te d\u2019Azur, Inria, CNRS, I3S, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3306-8314","authenticated-orcid":false,"given":"David","family":"Coudert","sequence":"additional","affiliation":[{"name":"Universit\u00e9 C\u00f4te d\u2019Azur, Inria, CNRS, I3S, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4500-5078","authenticated-orcid":false,"given":"Nicolas","family":"Nisse","sequence":"additional","affiliation":[{"name":"Universit\u00e9 C\u00f4te d\u2019Azur, Inria, CNRS, I3S, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,12,21]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SEA.2020.18"},{"key":"e_1_3_2_3_2","volume-title":"k Shortest Simple Paths (Version 2.0)","author":"Zoobi Ali Al","year":"2021","unstructured":"Ali Al Zoobi, David Coudert, and Nicolas Nisse. 2021. k Shortest Simple Paths (Version 2.0). Retrieved from https:\/\/gitlab.inria.fr\/dcoudert\/k-shortest-simple-paths"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0928-4869(00)00006-9"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-49487-6_2"},{"key":"e_1_3_2_6_2","first-page":"856","volume-title":"Proceedings of the International Conference on Acoustics, Speech, and Signal Processing","volume":"1","author":"Betz M.","year":"1995","unstructured":"M. Betz and H. Hild. 1995. Language models for a spelled letter recognizer. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, Vol. 1. IEEE, 856\u2013859. DOI:10.1109\/ICASSP.1995.479829"},{"issue":"4","key":"e_1_3_2_7_2","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/j.physrep.2005.10.009","article-title":"Complex networks: Structure and dynamics","volume":"424","author":"Boccaletti Stefano","year":"2006","unstructured":"Stefano Boccaletti, Vito Latora, Yamir Moreno, Martin Chavez, and D.-U. Hwang. 2006. Complex networks: Structure and dynamics. Phys. Rep. 424, 4-5 (2006), 175\u2013308.","journal-title":"Phys. Rep."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/0111081"},{"key":"e_1_3_2_9_2","unstructured":"Camil Demetrescu Andrew V. Goldberg and D. S. Johnson. 2006. 9th DIMACS Implementation Challenge\u2014Shortest Paths. Retrieved from http:\/\/users.diag.uniroma1.it\/challenge9\/"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795290477"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-2864-4_733"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.IPEC.2017.16"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.21552"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840439"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1048"},{"key":"e_1_3_2_16_2","first-page":"509","volume-title":"Proceedings of the 19th ACM International Conference on Information and Knowledge Management","author":"Gao Jun","year":"2010","unstructured":"Jun Gao, Huida Qiu, Xiao Jiang, Tengjiao Wang, and Dongqing Yang. 2010. Fast top-k simple shortest paths discovery in graphs. In Proceedings of the 19th ACM International Conference on Information and Knowledge Management. 509\u2013518."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.12.015"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199909)34:2<88::AID-NET2>3.0.CO;2-1"},{"key":"e_1_3_2_19_2","first-page":"9","article-title":"An  \\(O(n^3\\log {\\log {n}}\/\\log ^2{n})\\)  time algorithm for all pairs shortest paths","volume":"38","author":"Han Yijie","year":"2016","unstructured":"Yijie Han and Tadao Takaoka. 2016. An \\(O(n^3\\log {\\log {n}}\/\\log ^2{n})\\) time algorithm for all pairs shortest paths. J. Discrete Algor. 38 (2016), 9\u201319.","journal-title":"J. Discrete Algor."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290682"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2013.07.005"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/059\/11"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120406"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.17877\/DE290R-19814"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ISAAC.2016.49"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.18.7.401"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"e_1_3_2_28_2","article-title":"SNAP Datasets: Stanford Large Network Dataset Collection","author":"Leskovec Jure","year":"2014","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data","journal-title":"R"},{"issue":"1","key":"e_1_3_2_29_2","first-page":"D529\u2013D541","article-title":"The BioGRID interaction database: 2019 update","volume":"47","author":"Oughtred Rose","year":"2019","unstructured":"Rose Oughtred, Chris Stark, Bobby-Joe Breitkreutz, Jennifer Rust, Lorrie Boucher, Christie Chang, Nadine Kolas, Lara O\u2019Donnell, Genie Leung, Rochelle McAdam, et\u00a0al. 2019. The BioGRID interaction database: 2019 update. Nucleic Acids Res. 47, D1 (2019), D529\u2013D541.","journal-title":"Nucleic Acids Res."},{"issue":"1","key":"e_1_3_2_30_2","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/S0304-3975(03)00402-X","article-title":"A new approach to all-pairs shortest paths on real-weighted graphs","volume":"312","author":"Pettie Seth","year":"2004","unstructured":"Seth Pettie. 2004. A new approach to all-pairs shortest paths on real-weighted graphs. Theoret. Comput. Sci. 312, 1 (2004), 47\u201374.","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"e_1_3_2_31_2","first-page":"D449\u2013D451","article-title":"The database of interacting proteins: 2004 update","volume":"32","author":"Salwinski Lukasz","year":"2004","unstructured":"Lukasz Salwinski, Christopher S. Miller, Adam J. Smith, Frank K. Pettit, James U. Bowie, and David Eisenberg. 2004. The database of interacting proteins: 2004 update. Nucleic Acids Res. 32, suppl_1 (2004), D449\u2013D451.","journal-title":"Nucleic Acids Res."},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.1997.4.385"},{"issue":"3","key":"e_1_3_2_33_2","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1002\/net.3230090303","article-title":"On algorithms for finding the k shortest paths in a network","volume":"9","author":"Shier Douglas R.","year":"1979","unstructured":"Douglas R. Shier. 1979. On algorithms for finding the k shortest paths in a network. Networks 9, 3 (1979), 195\u2013214.","journal-title":"Networks"},{"key":"e_1_3_2_34_2","unstructured":"The Cooperative Association for Internet Data Analysis (CAIDA). 2013. The CAIDA AS Relationships Dataset. Retrieved from http:\/\/www.caida.org\/data\/active\/as-relationships\/"},{"key":"e_1_3_2_35_2","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1109\/FOCS.2010.67","volume-title":"Proceedings of the IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS\u201910)","author":"Williams Virginia Vassilevska","year":"2010","unstructured":"Virginia Vassilevska Williams and Ryan Williams. 2010. Subcubic equivalences between path, matrix and triangle problems. In Proceedings of the IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS\u201910). IEEE, 645\u2013654."},{"issue":"3","key":"e_1_3_2_36_2","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1111\/j.1538-4632.2007.00707.x","article-title":"Measuring the structure of road networks","volume":"39","author":"Xie Feng","year":"2007","unstructured":"Feng Xie and David Levinson. 2007. Measuring the structure of road networks. Geograph. Anal. 39, 3 (2007), 336\u2013356.","journal-title":"Geograph. Anal."},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2010.02.005"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.11.712"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626567","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626567","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:45Z","timestamp":1750178205000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626567"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,21]]},"references-count":37,"alternative-id":["10.1145\/3626567"],"URL":"https:\/\/doi.org\/10.1145\/3626567","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,21]]}}}