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
85217

Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs and Planar Graphs
Marek Karpinski, Miroslaw Kowaluk and Andrzej Lingas
[Download PostScript] [Download PDF]

The max-bisection problem is to find a partition of the vertices of agraph into two equal size subsets that maximizes the number of edges withendpoints in both subsets.We obtain new improved approximation ratios for the max-bisection problem onthe low degree k-regular graphs for 3 < k < 8, by deriving some improvedtransformations from a maximum cut into a maximum bisection partition. In thecase of three regular graphs we obtain an approximation ratios of 0.805, and 0.812, respectively.We also present the first polynomial time approximation scheme for themax-bisection problem for planar graphs of a sublinear degree.

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