|
 
|
[Ben05a] Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs
Conférence Internationale avec comité de lecture : ICGT'05 7th Int. Colloquium on Graph Theory, Hyères, January 2005, Vol. 22, pp.55-60, Series ENDM, (DOI: 10.1016/j.endm.2005.06.010)
motcle:
Résumé:
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), pp. 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.
Equipe:
oc
BibTeX
| @inproceedings { | |||
| Ben05a, | |||
| title | = | "{Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs}", | |
| author | = | " C. Bentz ", | |
| booktitle | = | "{ICGT'05 7th Int. Colloquium on Graph Theory, Hyères}", | |
| year | = | 2005, | |
| month | = | "January", | |
| series | = | "ENDM", | |
| volume | = | 22, | |
| pages | = | "55-60", | |
| doi | = | "10.1016/j.endm.2005.06.010", | |
| } | |||
