Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

K-Shortest Simple Paths Using Biobjective Path Search

  • In this paper we introduce a new algorithm for the k-Shortest Simple Paths (K-SSP) problem with an asymptotic running time matching the state of the art from the literature. It is based on a black-box algorithm due to Roditty and Zwick (2012) that solves at most 2k instances of the Second Shortest Simple Path (2-SSP) problem without specifying how this is done. We fill this gap using a novel approach: we turn the scalar 2-SSP into instances of the Biobjective Shortest Path problem. Our experiments on grid graphs and on road networks show that the new algorithm is very efficient in practice.

Export metadata

Additional Services

Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Pedro Maristany de las Casas, Antonio Sedeño-Noda, Ralf Borndörfer, Max Huneshagen
Document Type:Article
Parent Title (English):Mathematical Programming Computation
Volume:17
First Page:349
Last Page:384
Year of first publication:2025
ArXiv Id:http://arxiv.org/abs/2309.10377
DOI:https://doi.org/10.1007/s12532-025-00276-0
Licence (German):License LogoCreative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.