TY - GEN
A1 - Lindner, Niels
A1 - Maristany de las Casas, Pedro
A1 - Schiewe, Philine
T1 - Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data
N2 - We investigate preprocessing for single-source shortest path queries in digraphs, where arc costs are only known to lie in an interval. More precisely, we want to decide for each arc whether it is part of some shortest path tree for some realization of costs. We show that this problem is solvable in polynomial time by giving a combinatorial algorithm, using optimal structures that we call forks. Our algorithm turns out to be very efficient in practice, and is sometimes even superior in quality to a heuristic developed for the one-to-one shortest path problem in the context of passenger routing in public transport.
T3 - ZIB-Report - 21-17
KW - Preprocessing Shortest Path Problems
KW - Interval Data
KW - Graph Algorithms
Y1 - 2021
UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/8271
UR - https://nbn-resolving.org/urn:nbn:de:0297-zib-82716
SN - 1438-0064
ER -