|
 
|
[BEN05] Edge disjoint paths and multicut problems in graphs generalizing the trees
Rapport Scientifique : Date de dépot: 2005/01/01, (Tech. Rep.: CEDRIC-05-948)
motcle:
Résumé:
We generalize all the results obtained for trees in [N. Garg, V. Vazirani, M. Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in
trees. Algorithmica 18 (1997), pp. 3-20] to graphs with a fixed cyclomatic number. Moreover, we show that, for a fixed number of source-sink pairs, the minimum multicut problem is polynomial-time solvable in planar graphs and in bounded tree-width graphs. Eventually, we introduce the class of k-edge-outerplanar graphs and show that the integrality gap of the maximum edge-disjoint paths problem is bounded in these graphs.
BibTeX
| @techreport { | |||
| BEN05, | |||
| title | = | "{Edge disjoint paths and multicut problems in graphs generalizing the trees}", | |
| author | = | "C. Bentz", | |
| number | = | "{CEDRIC-05-948}", | |
| institution | = | "{CEDRIC laboratory, CNAM-Paris, France}", | |
| date | = | {01-01-2005}, | |
| } | |||
