Cuts and disjoint paths in the valley-free path model
OPEN ACCESS
Loading...
Author / Producer
Date
2003-09
Publication Type
Report
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
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 moti vated 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 ra tio is possible unless P = 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.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
180
Pages / Article No.
Publisher
ETH Zurich, Computer Engineering and Networks Laboratory
Event
Edition / version
Version 1
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.