The Undirected Two Disjoint Shortest Paths Problem

2018/09/11 by Gottschau, Marinus, Kaiser, Marcus, Waldmann, Clara
#05C85 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1809.03820

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.

Related

• A Polynomial Time Algorithm for the k-Disjoint Shortest Paths Problem
• Efficient Algorithms for Disjoint Shortest Paths Problem and its Extensions
• Detecting Disjoint Shortest Paths in Linear Time and More
• Shortest two disjoint paths in conservative graphs
• Shortest k-Disjoint Paths via Determinants