Two edge-disjoint paths with length constraints

摘要

We consider the problem of finding, for two pairs (s(1), t(1)) and (s(2) , t(2)) of vertices in an undirected graph, an (s(1), t(1))-path P-1 and an (s(2), t(2))-path P-2 such that P-1 and P-2 share no edges and the length of each P-i satisfies constraint L-i, where L-i is an element of { <= k(i), = k(i), >= k(i), (*)} with L-i = " *" indicating no length constraint on P-i.