Solving the Maximum Weight Planar Subgraph Problem by Branch-and-Cut

Jünger, Michael and Mutzel, Petra (1993) Solving the Maximum Weight Planar Subgraph Problem by Branch-and-Cut. [Preprint]

[img] Other
Download (91kB)

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: Preprint
Additional Information: This article was published in 1993 in the proceedings "Proceedings of the 3rd IPCO Conference (Integer Programming and Combinatorial Optimization)" (edited by Giovanni Rinaldi, L. Wolsey), pages 479-492.
Classifications: P Styles > P.540 Planar
G Algorithms and Complexity > G.840 Planarization
M Methods > M.700 Planarization-based
URI: http://gdea.informatik.uni-koeln.de/id/eprint/26

Actions (login required)

View Item View Item