The Undirected Two Disjoint Shortest Paths Problem

Marinus Gottschau, Marcus Kaiser, Clara Waldmann

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$…