ECCC-Report TR00-064https://eccc.weizmann.ac.il/report/2000/064Comments and Revisions published for TR00-064en-usTue, 29 Aug 2000 11:09:55 +0300
Paper TR00-064
| A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs |
Klaus Jansen,
Marek Karpinski,
Andrzej Lingas
https://eccc.weizmann.ac.il/report/2000/064The 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.
Tue, 29 Aug 2000 11:09:55 +0300https://eccc.weizmann.ac.il/report/2000/064