The undirected two disjoint shortest paths problem

DOI10.1016/J.ORL.2018.11.011zbMATH Open1476.05186arXiv1809.03820OpenAlexW2891649990WikidataQ128811765 ScholiaQ128811765MaRDI QIDQ2294271FDOQ2294271

Clara Waldmann, Marcus Kaiser, Marinus Gottschau

Publication date: 10 February 2020

Published in: Operations Research Letters (Search for Journal in Brave)

Abstract: The $k$ disjoint shortest paths problem ($k$-DSPP) on a graph with $k$ source-sink pairs $(s_i,t_i)$ asks for the existence of $k$ pairwise edge- or vertex-disjoint shortest $s_i$-$t_i$-paths. It is known to be NP-complete if $k$ is part of the input. Restricting to $2$-DSPP with strictly positive lengths, it becomes solvable in polynomial time. We extend this result by allowing zero edge lengths and give a polynomial time algorithm based on dynamic programming for $2$-DSPP on undirected graphs with non-negative edge lengths.

Full work available at URL: https://arxiv.org/abs/1809.03820

Recommendations

• Two disjoint shortest paths problem with non-negative edge length
• The Directed Disjoint Shortest Paths Problem
• The disjoint shortest paths problem
• On shortest disjoint paths in planar graphs
• STACS 2004

zbMATH Keywords

dynamic programmingmixed graphsdisjoint pathsdisjoint shortest paths

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Paths and cycles (05C38)

Cites Work

• Maximal Flow Through a Network
• The directed subgraph homeomorphism problem
• Graph minors. XIII: The disjoint paths problem
• On the Complexity of Timetable and Multicommodity Flow Problems
• Disjoint paths in a network
• On the Computational Complexity of Combinatorial Problems
• The disjoint shortest paths problem
• Shortest Two Disjoint Paths in Polynomial Time
• The Directed Disjoint Shortest Paths Problem

Cited In (14)

• The Directed Disjoint Shortest Paths Problem
• STACS 2004
• Title not available (Why is that?)
• Title not available (Why is that?)
• Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths
• The shortest path problem with two objective functions
• On the union of intermediate nodes of shortest paths
• The 2-disjoint path problem for circulant digraphs
• Finding non-dominated bicriteria shortest pairs of disjoint simple paths
• The directed 2-linkage problem with length constraints
• The complexity of routing problems in forbidden-transition graphs and edge-colored graphs
• The Maximum Disjoint Routing Problem
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: The undirected two disjoint shortest paths problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2294271)