Publication at Faculty of Mathematics and Physics |
2007
Abstract
In this paper we consider the $k$ edge-disjoint paths problem ($k$-EDP), a generalization of the well-known edge-disjoint paths problem. Given a graph $G=(V,E)$ and a set of terminal pairs (or requests) $T$, the problem is to find a maximum subset of the pairs in $T$ for which it is possible to select paths such that each pair is connected by $k$ edge-disjoint paths and the paths for different pairs are mutually disjoint.