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].


Download (226kB) | Preview


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])
CreatorsEmailORCIDORCID Put Code
Mutzel, PetraUNSPECIFIEDorcid.org/0000-0001-7621-971XUNSPECIFIED
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


Downloads per month over past year


Actions (login required)

View Item View Item