8271
eng
reportzib
0
--
2021-06-29
--
Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data
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.
1438-0064
urn:nbn:de:0297-zib-82716
10.4230/OASIcs.ATMOS.2021.7
publish
30.07.2021
appeared in 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)
Niels Lindner
Niels Lindner
Pedro Maristany de las Casas
Philine Schiewe
ZIB-Report
21-17
eng
uncontrolled
Preprocessing Shortest Path Problems
eng
uncontrolled
Interval Data
eng
uncontrolled
Graph Algorithms
Mathematics of Computing
Computer Applications
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Maristany de las Casas, Pedro
MODAL-Gesamt
Lindner, Niels
Network Optimization
MODAL-MobilityLab
https://opus4.kobv.de/opus4-zib/files/8271/ZR-21-17.pdf