The shortest disjoint paths problem

12/22/2019

∙

by   William Lochet, et al.

∙

0

∙

share

For any fixed k, we show the existence of a polynomial-time algorithm deciding if, given a graph G and a set of pairs of vertices (s_1, t_1), ..., (s_k, t_k), there exist k vertex-disjoint paths from s_i to t_i such that each of these paths is a shortest path.