Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9514527 | Electronic Notes in Discrete Mathematics | 2005 | 6 Pages |
Abstract
We generalize all the results obtained for integer multiflow and multicut problems in trees by Garg et al. [N. Garg, V.V. Vazirani and M. Yannakakis, Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18 (1997) 3-20] to planar graphs with a fixed number of faces, although other classical generalizations do not lead to such results. We also introduce the class of k-edge-outerplanar graphs and bound the integrality gap for the maximum edge-disjoint paths problem in these graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Cédric Bentz,