|
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 |