@inproceedings{632,
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.}},
author = {{Kolman, Petr and Scheideler, Christian}},
booktitle = {{Proceedings of the 23th ACM SIAM Symposium on Discrete Algorithms (SODA)}},
pages = {{800--810}},
title = {{{Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case}}},
doi = {{10.1137/1.9781611973099.64}},
year = {{2012}},
}