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

K-Shortest Simple Paths Using Biobjective Path Search

under review
  • 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

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Author:Pedro Maristany de las Casas, Antonio Sedeño-Noda, Ralf Borndörfer, Max Huneshagen
Document Type:Article
Parent Title (English):Arxiv Preprint
Year of first publication:2023
ArXiv Id:http://arxiv.org/abs/2309.10377
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.