---
res:
bibo_abstract:
- 'Given an integer h, a graph G = (V;E) with arbitrary positive edge capacities
and k pairs of vertices (s1; t1); (s2; t2); : : : ; (sk; tk), called terminals,
an h-route cut is a set F µ E of edges such that after the removal of the edges
in F no pair si ¡ ti is connected by h edge-disjoint paths (i.e., the connectivity
of every si ¡ ti pair is at most h ¡ 1 in (V;E n F)). The h-route cut is a natural
generalization of the classical cut problem for multicommodity °ows (take h =
1). The main result of this paper is an O(h722h log2 k)-approximation algorithm
for the minimum h-route cut problem in the case that s1 = s2 = ¢ ¢ ¢ = sk, called
the single source case. As a corollary of it we obtain an approximate duality
theorem for multiroute multicom-modity °ows and cuts with a single source. This
partially answers an open question posted in several previous papers dealing with
cuts for multicommodity multiroute problems.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Petr
foaf_name: Kolman, Petr
foaf_surname: Kolman
- foaf_Person:
foaf_givenName: Christian
foaf_name: Scheideler, Christian
foaf_surname: Scheideler
foaf_workInfoHomepage: http://www.librecat.org/personId=20792
bibo_doi: 10.1137/1.9781611973099.64
dct_date: 2012^xs_gYear
dct_title: 'Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single
Source Case@'
...