Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2000 Copyright 2000 University of Bonn, Department of Computer Science, 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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V