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

P. Kolman, C. Scheideler, in: Proceedings of the 23th ACM SIAM Symposium on Discrete Algorithms (SODA), 2012, pp. 800–810.

Download
Restricted 632-SODA2012-Scheideler_01.pdf 220.21 KB
Conference Paper
Author
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.
Publishing Year
Proceedings Title
Proceedings of the 23th ACM SIAM Symposium on Discrete Algorithms (SODA)
Page
800-810
LibreCat-ID
632

Cite this

Kolman P, Scheideler C. Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case. In: Proceedings of the 23th ACM SIAM Symposium on Discrete Algorithms (SODA). ; 2012:800-810. doi:10.1137/1.9781611973099.64
Kolman, P., & Scheideler, C. (2012). Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case. In Proceedings of the 23th ACM SIAM Symposium on Discrete Algorithms (SODA) (pp. 800–810). https://doi.org/10.1137/1.9781611973099.64
@inproceedings{Kolman_Scheideler_2012, title={Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case}, DOI={10.1137/1.9781611973099.64}, booktitle={Proceedings of the 23th ACM SIAM Symposium on Discrete Algorithms (SODA)}, author={Kolman, Petr and Scheideler, Christian}, year={2012}, pages={800–810} }
Kolman, Petr, and Christian Scheideler. “Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case.” In Proceedings of the 23th ACM SIAM Symposium on Discrete Algorithms (SODA), 800–810, 2012. https://doi.org/10.1137/1.9781611973099.64.
P. Kolman and C. Scheideler, “Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case,” in Proceedings of the 23th ACM SIAM Symposium on Discrete Algorithms (SODA), 2012, pp. 800–810.
Kolman, Petr, and Christian Scheideler. “Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case.” Proceedings of the 23th ACM SIAM Symposium on Discrete Algorithms (SODA), 2012, pp. 800–10, doi:10.1137/1.9781611973099.64.
Main File(s)
File Name
632-SODA2012-Scheideler_01.pdf 220.21 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-15T06:35:58Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar