| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 437184 | Theoretical Computer Science | 2006 | 4 Pages |
Abstract
We present a pure combinatorial problem whose solution determines max-flow min-cut ratio for directed multicommodity flows. In addition, this combinatorial problem has applications in improving the approximation factor of the greedy algorithm for the maximum edge disjoint path problem. More precisely, our upper bound improves the approximation factor for this problem to O(n3/4).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
