TR00-064 Authors: Klaus Jansen, Marek Karpinski, Andrzej Lingas

Publication: 29th August 2000 11:09

Downloads: 1857

Keywords:

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 maximize or minimize, 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. The method of solution

involves designing exact polynomial time algorithms for computing optimal

partitions of bounded treewidth graphs, in particular their Max- and

Min-Bisection, which could be also of independent interest.