Short Length Menger's Theorem and Reliable Optical Routing

Abstrakt

We deal with a generalization of the minimum path coloring problem: given a graph and a set of pairs of vertices, we are asked to connect each pair by $k$ edge disjoint paths of the same color; the objective is to minimize the number of colors while maintaining the property that paths of the same color are edge disjoint. The underlying problem is that of finding several disjoint paths between a given pair of vertices, which is closely related to the Menger's theorem.

The Menger's theorem does not say anything about the length of the paths; the question about the length of the paths is also addressed in the paper.