Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs
Bentz, Cédric · HAL - CNAM · 2005
We generalize all the results obtained for integer multiflow andmulticut problems in trees by Garg et al. [N. Garg, V.V. Vazirani and M. Yannakakis. Primal-dual approximation algorithms for integral flow and multicut intrees. Algorithmica 18 (1997), pp. 3-20] to planargraphs with a fixed number of faces, although other classicalgeneralizations do not lead to such results. We also introduce theclass of k-edge-outerplanar graphs and bound theintegrality gap for the maximum edge-disjoint paths problem inthese graphs.