The undirected two disjoint shortest paths problem

DOI10.1016/J.ORL.2018.11.011MaRDI QIDQ2294271zbMATH OpenOpenAlexWikidataFDO

Authors Marinus Gottschau, Marcus Kaiser, Clara Waldmann

Publication date 10 February 2020

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

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

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)

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.

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

Cites work

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

Cited in

(18)

• scientific article; zbMATH DE number 1409242 (Why is no real title available?)
• The Directed Disjoint Shortest Paths Problem
• STACS 2004
• scientific article; zbMATH DE number 7765417 (Why is no real title available?)
• Exact algorithms for finding partial edge-disjoint paths
• A note on \(k\)-shortest paths problem
• scientific article; zbMATH DE number 1517139 (Why is no real title available?)
• Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths
• The shortest path problem with two objective functions
• Two disjoint shortest paths problem with non-negative edge length
• 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
• scientific article; zbMATH DE number 3922000 (Why is no real title available?)
• Computing disjoint paths with length constraints

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)