Improved bounds on the max-flow min-cut ratio for multicommodity flows
- 1 January 1993
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 691-697
- https://doi.org/10.1145/167088.167263
Abstract
In this paper we consider the worst case ratio between the capacity of min-cuts and the valueof max-flow for multicommodity flow problems. We improve the best known bounds for the mincutmax-flow ratio for multicommodity flows in undirected graphs, by replacing the O(log D) inthe bound by O(log k), where D denotes the sum of all demands, and k denotes the number ofcommodities. In essence we prove that up to constant factors the worst min-cut max-flow ratiosappear in problems where...Keywords
This publication has 0 references indexed in Scilit: