Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420477 | Discrete Applied Mathematics | 2009 | 11 Pages |
Abstract
We generalize all the results obtained for maximum integer multiflow and minimum multicut problems in trees by Garg, Vazirani and Yannakakis [N. Garg, V.V. Vazirani, M. Yannakakis, Primal-dual approximation algorithms for integral flow and multicut in trees, Algorithmica 18 (1997) 3–20] to graphs with a fixed cyclomatic number, while this cannot be achieved for other classical generalizations of trees. We also introduce thekk-edge-outerplanar graphs, a class of planar graphs with arbitrary (but bounded) tree-width that generalizes the cacti, and show that the integrality gap of the maximum edge-disjoint paths problem is bounded in these graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Cédric Bentz,