DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2026.8

Finding Maximum-Success Disjoint Paths

Authors: Aaron Neugebauer and Marie Schmidt

Published in: OASIcs, Volume 147, 26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026)

Abstract

Motivated by challenges occurring in disaster relief operations, we study the problem to find two edge-disjoint paths in a graph whose arcs are labeled with traversability probabilities that maximize the probability that (at least) one of the paths is traversable. We show that this problem is NP-hard. To solve the problem, we propose to model it as a bi-objective problem, taking traversability probabilities of the two individual paths as objective functions. We show that an optimal solution to our problem is an extreme-supported solution of the so defined bi-objective problem and exploit this property to find optimal solutions. Furthermore, we present two approximation approaches, and compare the approaches experimentally with respect to runtime and solution quality.

Cite as

Aaron Neugebauer and Marie Schmidt. Finding Maximum-Success Disjoint Paths. In 26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026). Open Access Series in Informatics (OASIcs), Volume 147, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{neugebauer_et_al:OASIcs.ATMOS.2026.8,
  author =	{Neugebauer, Aaron and Schmidt, Marie},
  title =	{{Finding Maximum-Success Disjoint Paths}},
  booktitle =	{26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026)},
  pages =	{8:1--8:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-453-6},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{147},
  editor =	{Cacchiani, Valentina and Funke, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2026.8},
  URN =		{urn:nbn:de:0030-drops-278048},
  doi =		{10.4230/OASIcs.ATMOS.2026.8},
  annote =	{Keywords: Route finding under uncertainty, Edge-disjoint paths, Optimization, Exact algorithms, Approximation algorithms, Vectorization}
}

Search Results

Documents authored by Neugebauer, Aaron

Finding Maximum-Success Disjoint Paths

Abstract

Cite as

Thanks for your feedback!

Could not send message