2026-07-20T14:48:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14876 2024-03-06T10:31:35Z ddc:004 open_access

Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data Lindner, Niels Maristany de las Casas, Pedro Schiewe, Philine Preprocessing Shortest Path Problems Interval Data Graph Algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Niels Lindner and Pedro Maristany de las Casas and Philine Schiewe 2021 Is Part Of OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2021.7 urn:nbn:de:0030-drops-148767 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.7 eng https://creativecommons.org/licenses/by/4.0/legalcode