Universität zu Köln

Huang, Chien-Chung, Mari, Mathieu, Mathieu, Claire, Schewior, Kevin and Vygen, Jens (2021). AN APPROXIMATION ALGORITHM FOR FULLY PLANAR EDGE-DISJOINT PATHS. SIAM Discret. Math., 35 (2). S. 752 - 770. PHILADELPHIA: SIAM PUBLICATIONS. ISSN 1095-7146

Full text not available from this repository.

Abstract

We devise a constant-factor approximation algorithm for the maximization version of the edge-disjoint paths problem if the supply graph together with the demand edges forms a planar graph. By planar duality, this is equivalent to packing cuts in a planar graph such that each cut contains exactly one demand edge. We also show that the natural linear programming relaxations have constant integrality gap, yielding an approximate max-multiflow min-multicut theorem.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Huang, Chien-Chung UNSPECIFIED UNSPECIFIED UNSPECIFIED Mari, Mathieu UNSPECIFIED UNSPECIFIED UNSPECIFIED Mathieu, Claire UNSPECIFIED UNSPECIFIED UNSPECIFIED Schewior, Kevin UNSPECIFIED UNSPECIFIED UNSPECIFIED Vygen, Jens UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-590416
DOI:	10.1137/20M1319401
Journal or Publication Title:	SIAM Discret. Math.
Volume:	35
Number:	2
Page Range:	S. 752 - 770
Date:	2021
Publisher:	SIAM PUBLICATIONS
Place of Publication:	PHILADELPHIA
ISSN:	1095-7146
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language ODD CYCLES; MULTICUT; FLOW; THEOREMS; HARDNESS; RATIO; CUTS Multiple languages Mathematics, Applied Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/59041