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

Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data

Please always quote using this URN: urn:nbn:de:0297-zib-82716
  • 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.

Download full text files

Export metadata

Metadaten
Author:Niels LindnerORCiD, Pedro Maristany de las CasasORCiD, Philine SchieweORCiD
Document Type:ZIB-Report
Tag:Graph Algorithms; Interval Data; Preprocessing Shortest Path Problems
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
CCS-Classification:G. Mathematics of Computing
J. Computer Applications
Date of first Publication:2021/06/29
Series (Serial Number):ZIB-Report (21-17)
ISSN:1438-0064
Published in:appeared in 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)
DOI:https://doi.org/10.4230/OASIcs.ATMOS.2021.7
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.