Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2000 Copyright 2000 Universität Bonn, Institut für Informatik, Abt. V

A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs
Klaus Jansen, Marek Karpinski and Andrzej Lingas
[Download PostScript] [Download PDF]

The Max-Bisection and Min-Bisection are the problems of finding partitions of the vertices of a given graph into two equal size subsets so as to maximizes or minimizes, respectively, the number of edges with exactly one endpoint in each subset. In this paper we design the first polynomial time approximation scheme for the Max-Bisection problem on arbitrary planar graphs solving a long time standing open problem. The method of solution involves a design of exact polynomial time algorithms for computing optimal partitions of bounded treewidth graphs, in particular their Max- and Min-Bisections, which could be also of independent interest.

Last Change: 11/05/14 at 10:16:50
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope