Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case

Petr Kolman and Christian Scheideler


Given an integer h, a graph with arbitrary positive edge capacities and k pairs of vertices , called terminals, an h-route cut is a set of edges such that after the removal of the edges in F no pair is connected by h edge-disjoint paths (i.e., the connectivity of every pair is at most in . The h-route cut is a natural generalization of the classical cut problem for multicommodity flows (take h = 1). The main result of this paper is an -approximation algorithm for the minimum h-route cut problem in the case that , called the single source case. As a corollary of it we obtain an approximate duality theorem for multiroute multicommodity flows and cuts with a single source. This partially answers an open question posted in several previous papers dealing with cuts for multicommodity multiroute problems.

Guest: Christian Scheideler
Host: Shantanu Das

Leave a Reply

Your email address will not be published.

165,457 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>