 |
|
|||
| Authors: | Thomas Erlebach, Alexander Hall, Alessandro Panconesi, Danica Vukadinovic-Greetham |
| Group: | Theory of Communication Networks |
| Type: | Techreport |
| Title: | Cuts and Disjoint Paths in the Valley-Free Path Model |
| Year: | 2003 |
| Month: | September |
| Pub-Key: | EHPV03tr |
| Rep Nbr: | 180 |
| Abstract: | In the valley-free path model, a path in a given directed graph is valid if it consists of a sequence of forward edges followed by a sequence of backward edges. This model is motivated by routing policies of autonomous systems in the Internet. We give a $2$-approximation algorithm for the problem of computing a maximum number of edge- or vertex-disjoint valid paths between two given vertices $s$ and $t$, and we show that no better approximation ratio is possible unless $PP=NP$. Furthermore, we give a $2$-approximation for the problem of computing a minimum vertex cut that separates $s$ and $t$ with respect to all valid paths and prove that the problem is APX-hard. The corresponding problem for edge cuts is shown to be polynomial-time solvable. We present additional results for acyclic graphs. |
| Resources: | [BibTeX] [Paper as PDF] |
