TY  - JOUR
U1  - Wissenschaftlicher Artikel
A1  - Maristany de las Casas, Pedro
A1  - Sedeño-Noda, Antonio
A1  - Borndörfer, Ralf
A1  - Huneshagen, Max
T1  - K-shortest simple paths using biobjective path search
JF  - Mathematical Programming Computation
N2  - 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 liter-
ature. It is based on a black-box algorithm due to Roditty and Zwick [30] 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.
AB  - 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 liter-
ature. It is based on a black-box algorithm due to Roditty and Zwick [30] 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.
Y1  - 2025
SN  - 1867-2949
SS  - 1867-2949
U6  - https://doi.org/10.1007/s12532-025-00276-0
DO  - https://doi.org/10.1007/s12532-025-00276-0
VL  - 17
IS  - 2
SP  - 349
EP  - 384
S1  - 36
PB  - Springer Science and Business Media LLC
ER  -