{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T07:05:31Z","timestamp":1784012731126,"version":"3.55.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T00:00:00Z","timestamp":1739404800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T00:00:00Z","timestamp":1739404800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Prog. Comp."],"published-print":{"date-parts":[[2025,6]]},"DOI":"10.1007\/s12532-025-00276-0","type":"journal-article","created":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T06:21:06Z","timestamp":1739427666000},"page":"349-384","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["K-shortest simple paths using biobjective path search"],"prefix":"10.1007","volume":"17","author":[{"given":"Pedro","family":"Maristany de las Casas","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Antonio","family":"Sede\u00f1o-Noda","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ralf","family":"Bornd\u00f6rfer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Max","family":"Huneshagen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,2,13]]},"reference":[{"key":"276_CR1","doi-asserted-by":"publisher","unstructured":"Ahmadi, S., Tack, G., Harabor, D., Kilby, P.: Bi-objective search with bi-directional A*. In: P.\u00a0Mutzel, R.\u00a0Pagh, G.\u00a0Herman (eds.) 29th Annual European Symposium on Algorithms (ESA 2021), Leibniz International Proceedings in Informatics (LIPIcs), vol. 204, pp. 3:1\u20133:15. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2021.3","DOI":"10.4230\/LIPIcs.ESA.2021.3"},{"key":"276_CR2","doi-asserted-by":"publisher","unstructured":"Al\u00a0Zoobi, A., Coudert, D., Nisse, N.: Space and Time Trade-Off for the k Shortest Simple Paths Problem. In: S.\u00a0Faro, D.\u00a0Cantone (eds.) 18th International Symposium on Experimental Algorithms (SEA 2020), Leibniz International Proceedings in Informatics (LIPIcs), vol. 160, pp. 18:1\u201318:13. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2020).https:\/\/doi.org\/10.4230\/LIPIcs.SEA.2020.18","DOI":"10.4230\/LIPIcs.SEA.2020.18"},{"key":"276_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3626567","volume":"28","author":"A Al Zoobi","year":"2023","unstructured":"Al Zoobi, A., Coudert, D., Nisse, N.: Finding the k shortest simple paths: time and space trade-offs. ACM J. Exp. Algorithmics 28, 1\u201323 (2023). https:\/\/doi.org\/10.1145\/3626567","journal-title":"ACM J. Exp. Algorithmics"},{"key":"276_CR4","doi-asserted-by":"publisher","unstructured":"B\u00f6kler, F.K.: Output-sensitive complexity of multiobjective combinatorial optimization with an application to the multiobjective shortest path problem. Ph.D. thesis, Technische Universit\u00e4t Dortmund (2018).https:\/\/doi.org\/10.17877\/DE290R-19130","DOI":"10.17877\/DE290R-19130"},{"key":"276_CR5","doi-asserted-by":"publisher","unstructured":"Casas, P.M.D.L.: maristanyPedro\/kshortestpaths: Initial Release \u2013 Preprint Citation (2023). https:\/\/doi.org\/10.5281\/zenodo.8324671","DOI":"10.5281\/zenodo.8324671"},{"key":"276_CR6","doi-asserted-by":"publisher","unstructured":"Casas, P.M.D.L., Bornd\u00f6rfer, R., Kraus, L., Sede\u00f1o Noda, A.: An FPTAS for Dynamic Multiobjective Shortest Path Problems. Algorithms 14(2) (2021). https:\/\/doi.org\/10.3390\/a14020043","DOI":"10.3390\/a14020043"},{"key":"276_CR7","doi-asserted-by":"publisher","unstructured":"Casas, P.M.D.L., Kraus, L., Sede\u00f1o Noda, A., Bornd\u00f6rfer, R.: Targeted multiobjective Dijkstra algorithm. Networks (2023). https:\/\/doi.org\/10.1002\/net.22174","DOI":"10.1002\/net.22174"},{"key":"276_CR8","doi-asserted-by":"publisher","unstructured":"Casas, P.M.D.L., Sede\u00f1o Noda, A., Bornd\u00f6rfer, R.: An improved multiobjective shortest path algorithm. Comput. Oper. Rese. 135, 105424 (2021). https:\/\/doi.org\/10.1016\/j.cor.2021.105424","DOI":"10.1016\/j.cor.2021.105424"},{"key":"276_CR9","doi-asserted-by":"crossref","unstructured":"Clarke, S., Krikorian, A., Rausen, J.: Computing the n best loopless paths in a network. J. Soc. Ind. Appl. Math. 11(4), 1096\u20131102 (1963). http:\/\/www.jstor.org\/stable\/2946497","DOI":"10.1137\/0111081"},{"key":"276_CR10","unstructured":"Demetrescu, C., Goldberg, A., Johnson, D.: 9th DIMACS implementation challenge - shortest paths. http:\/\/www.diag.uniroma1.it\/\/challenge9\/ (2009). Accessed: 2021-12-15"},{"issue":"1","key":"276_CR11","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/bf01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik 1 1(1), 269\u2013271 (1959). https:\/\/doi.org\/10.1007\/bf01386390","journal-title":"Numerische Mathematik 1"},{"key":"276_CR12","doi-asserted-by":"publisher","unstructured":"Ehrgott, M.: Multicriteria Optimization. Springer, Berlin (2005). https:\/\/doi.org\/10.1007\/3-540-27659-9","DOI":"10.1007\/3-540-27659-9"},{"issue":"2","key":"276_CR13","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1137\/s0097539795290477","volume":"28","author":"D Eppstein","year":"1998","unstructured":"Eppstein, D.: Finding the k Shortest Paths. SIAM J. Comput. 28(2), 652\u2013673 (1998). https:\/\/doi.org\/10.1137\/s0097539795290477","journal-title":"SIAM J. Comput."},{"key":"276_CR14","doi-asserted-by":"publisher","unstructured":"Eppstein, D.: k-Best enumeration. In: Encyclopedia of algorithms, pp. 1003\u20131006. Springer New York, New York, NY (2016).https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_733","DOI":"10.1007\/978-1-4939-2864-4_733"},{"issue":"1","key":"276_CR15","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1002\/net.21552","volume":"64","author":"G Feng","year":"2014","unstructured":"Feng, G.: Finding k shortest simple paths in directed graphs: A node classification algorithm. Networks 64(1), 6\u201317 (2014). https:\/\/doi.org\/10.1002\/net.21552","journal-title":"Networks"},{"issue":"10","key":"276_CR16","doi-asserted-by":"publisher","first-page":"2459","DOI":"10.1109\/TC.2013.136","volume":"63","author":"G Feng","year":"2014","unstructured":"Feng, G.: Improving space efficiency with path length prediction for finding $$k$$ shortest simple paths. IEEE Trans. Comput. 63(10), 2459\u20132472 (2014). https:\/\/doi.org\/10.1109\/TC.2013.136","journal-title":"IEEE Trans. Comput."},{"issue":"1\u20132","key":"276_CR17","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1002\/mcda.1574","volume":"24","author":"JR Figueira","year":"2016","unstructured":"Figueira, J.R., Fonseca, C.M., Halffmann, P., Klamroth, K., Paquete, L., Ruzika, S., Schulze, B., Stiglmayr, M., Willems, D.: Easy to say they are hard, but hard to see they are easy- towards a categorization of tractable multiobjective combinatorial optimization problems: easy to say they are hard, but hard to see they are easy. J. Multi-Criteria Decis. Anal. 24(1\u20132), 82\u201398 (2016). https:\/\/doi.org\/10.1002\/mcda.1574","journal-title":"J. Multi-Criteria Decis. Anal."},{"issue":"3","key":"276_CR18","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"ML Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596\u2013615 (1987). https:\/\/doi.org\/10.1145\/28869.28874","journal-title":"J. ACM"},{"issue":"7","key":"276_CR19","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1016\/j.ipl.2008.12.015","volume":"109","author":"Z Gotthilf","year":"2009","unstructured":"Gotthilf, Z., Lewenstein, M.: Improved algorithms for the k simple shortest paths and the replacement paths problems. Inf. Process. Lett. 109(7), 352\u2013355 (2009). https:\/\/doi.org\/10.1016\/j.ipl.2008.12.015","journal-title":"Inf. Process. Lett."},{"key":"276_CR20","doi-asserted-by":"publisher","unstructured":"Hansen, P.: Bicriterion Path Problems. In: G.\u00a0Fandel, T.\u00a0Gal (eds.) Multiple criteria decision making theory and application, pp. 109\u2013127. Springer, Berlin (1980).https:\/\/doi.org\/10.1007\/978-3-642-48782-8_9","DOI":"10.1007\/978-3-642-48782-8_9"},{"key":"276_CR21","doi-asserted-by":"publisher","unstructured":"Kurz, D., Mutzel, P.: A Sidetrack-Based Algorithm for Finding the k Shortest Simple Paths in a Directed Graph. In: S.H. Hong (ed.) 27th International Symposium on Algorithms and Computation (ISAAC 2016), Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a064, pp. 49:1\u201349:13. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2016)https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2016.49. https:\/\/drops.dagstuhl.de\/entities\/document\/10.4230\/LIPIcs.ISAAC.2016.49","DOI":"10.4230\/LIPIcs.ISAAC.2016.49"},{"key":"276_CR22","doi-asserted-by":"crossref","unstructured":"Lawler, E.L.: A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem. Manag. Sci. 18(7), 401\u2013405 (1972). http:\/\/www.jstor.org\/stable\/2629357","DOI":"10.1287\/mnsc.18.7.401"},{"issue":"2","key":"276_CR23","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1016\/0377-2217(84)90077-8","volume":"16","author":"EQV Martins","year":"1984","unstructured":"Martins, E.Q.V.: On a multicriteria shortest path problem. Eur. J. Oper. Res. 16(2), 236\u2013245 (1984). https:\/\/doi.org\/10.1016\/0377-2217(84)90077-8","journal-title":"Eur. J. Oper. Res."},{"key":"276_CR24","doi-asserted-by":"publisher","unstructured":"Martins, E.Q.V., Pascoal, M.M.B.: A new implementation of Yen\u2019s ranking loopless paths algorithm. Quart. J. Belgian, French and Italian Oper. Res. Soc. 1(2) (2003).https:\/\/doi.org\/10.1007\/s10288-002-0010-2","DOI":"10.1007\/s10288-002-0010-2"},{"issue":"03","key":"276_CR25","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1142\/s0129054199000186","volume":"10","author":"EQV Martins","year":"1999","unstructured":"Martins, E.Q.V., Pascoal, M.M.B., Santos, J.L.: Deviation algorithms for ranking shortest paths. Int. J. Found. Comput. Sci. 10(03), 247\u2013261 (1999). https:\/\/doi.org\/10.1142\/s0129054199000186","journal-title":"Int. J. Found. Comput. Sci."},{"key":"276_CR26","doi-asserted-by":"publisher","unstructured":"Orlin, J.B., V\u00e9gh, L.: Directed shortest paths via approximate cost balancing. J. ACM 70(1) (2022).https:\/\/doi.org\/10.1145\/3565019","DOI":"10.1145\/3565019"},{"key":"276_CR27","doi-asserted-by":"publisher","unstructured":"Pettie, S.: A new approach to all-pairs shortest paths on real-weighted graphs. Theoret. Comput. Sci. 312(1), 47\u201374 (2004).https:\/\/doi.org\/10.1016\/S0304-3975(03)00402-X. Automata, Languages and Programming","DOI":"10.1016\/S0304-3975(03)00402-X"},{"issue":"1","key":"276_CR28","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.ejor.2014.05.008","volume":"239","author":"FJ Pulido","year":"2014","unstructured":"Pulido, F.J., Mandow, L., de la Cruz, J.L.P.: Multiobjective shortest path problems with lexicographic goal-based preferences. Eur. J. Oper. Res. 239(1), 89\u2013101 (2014). https:\/\/doi.org\/10.1016\/j.ejor.2014.05.008","journal-title":"Eur. J. Oper. Res."},{"key":"276_CR29","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/11523468_21","volume-title":"Automata, Languages and Programming","author":"L Roditty","year":"2005","unstructured":"Roditty, L., Zwick, U.: Replacement paths and k simple shortest paths in unweighted directed graphs. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) Automata, Languages and Programming, pp. 249\u2013260. Springer, Berlin (2005)"},{"key":"276_CR30","doi-asserted-by":"publisher","unstructured":"Roditty, L., Zwick, U.: Replacement paths and k simple shortest paths in unweighted directed graphs. ACM Trans. Algorithms 8(4) (2012).https:\/\/doi.org\/10.1145\/2344422.2344423","DOI":"10.1145\/2344422.2344423"},{"issue":"05","key":"276_CR31","doi-asserted-by":"publisher","first-page":"1650042","DOI":"10.1142\/s0217595916500421","volume":"33","author":"A Sede\u00f1o Noda","year":"2016","unstructured":"Sede\u00f1o Noda, A.: Ranking one million simple paths in road networks. Asia-Pacific J. Oper. Res. 33(05), 1650042 (2016). https:\/\/doi.org\/10.1142\/s0217595916500421","journal-title":"Asia-Pacific J. Oper. Res."},{"issue":"1","key":"276_CR32","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/j.ejor.2019.01.007","volume":"276","author":"A Sede\u00f1o Noda","year":"2019","unstructured":"Sede\u00f1o Noda, A., Colebrook, M.: A Biobjective Dijkstra algorithm. Eur. J. Oper. Res. 276(1), 106\u2013118 (2019). https:\/\/doi.org\/10.1016\/j.ejor.2019.01.007","journal-title":"Eur. J. Oper. Res."},{"issue":"5","key":"276_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3186893","volume":"65","author":"V Vassilevska Williams","year":"2018","unstructured":"Vassilevska Williams, V., Williams, R.R.: Subcubic equivalences between path, matrix, and triangle problems. J. ACM 65(5), 1\u201338 (2018). https:\/\/doi.org\/10.1145\/3186893","journal-title":"J. ACM"},{"issue":"3","key":"276_CR34","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1145\/321707.321712","volume":"19","author":"JY Yen","year":"1972","unstructured":"Yen, J.Y.: Finding the lengths of all shortest paths in N-node nonnegative-distance complete networks using $$1\/2$$ N3 additions and N3 comparisons. J. ACM (JACM) 19(3), 423\u2013424 (1972). https:\/\/doi.org\/10.1145\/321707.321712","journal-title":"J. ACM (JACM)"}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-025-00276-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12532-025-00276-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-025-00276-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,16]],"date-time":"2025-05-16T11:23:15Z","timestamp":1747394595000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12532-025-00276-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,13]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["276"],"URL":"https:\/\/doi.org\/10.1007\/s12532-025-00276-0","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"value":"1867-2949","type":"print"},{"value":"1867-2957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,13]]},"assertion":[{"value":"24 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 November 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 February 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}