License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2021.7
URN: urn:nbn:de:0030-drops-148767
URL: https://drops.dagstuhl.de/opus/volltexte/2021/14876/
Go to the corresponding OASIcs Volume Portal


Lindner, Niels ; Maristany de las Casas, Pedro ; Schiewe, Philine

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

pdf-format:
OASIcs-ATMOS-2021-7.pdf (0.8 MB)


Abstract

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.

BibTeX - Entry

@InProceedings{lindner_et_al:OASIcs.ATMOS.2021.7,
  author =	{Lindner, Niels and Maristany de las Casas, Pedro and Schiewe, Philine},
  title =	{{Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{7:1--7:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14876},
  URN =		{urn:nbn:de:0030-drops-148767},
  doi =		{10.4230/OASIcs.ATMOS.2021.7},
  annote =	{Keywords: Preprocessing Shortest Path Problems, Interval Data, Graph Algorithms}
}

Keywords: Preprocessing Shortest Path Problems, Interval Data, Graph Algorithms
Collection: 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)
Issue Date: 2021
Date of publication: 27.09.2021
Supplementary Material: Software (Source Code): https://github.com/tfePedro/optimal-forks archived at: https://archive.softwareheritage.org/swh:1:dir:f2f5d9db0b2228b799ca2d48dd9deff901f89725


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI