Universität zu Köln

Jünger, Michael and Mutzel, Petra ORCID: 0000-0001-7621-971X (1993). Solving the Maximum Weight Planar Subgraph Problem by Branch-and-Cut. IPCO Conference. ["eprint_fieldopt_monograph_type_preprint" not defined].

Preview

PDF zpr93-128.pdf Download (226kB) | Preview

Abstract

In this paper we investigate the problem of identifying a planar subgraph of maximum weight of a given edge weighted graph. In the theoretical part of the paper, the polytope of all planar subgraphs of a graph G is defined and studied. All subgraphs of a graph G, which are subdivisions of K5 or K3,3, turn out to define facets of this polytope. We also present computational experience with a branch-and-cut algorithm for the above problem. Our approach is based on an algorithm which searches for forbidden substructures in a graph that contains a subdivision of K5 or K3,3. These structures give us inequalities which are used as cutting planes.

Item Type:	Preprints, Working Papers or Reports (["eprint_fieldopt_monograph_type_preprint" not defined])
Creators:	Creators Email ORCID ORCID Put Code Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Mutzel, Petra UNSPECIFIED orcid.org/0000-0001-7621-971X UNSPECIFIED
URN:	urn:nbn:de:hbz:38-546782
Page Range:	pp. 479-492
Date:	1993
Publisher:	IPCO Conference
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54678