ECCC-Report TR00-051https://eccc.weizmann.ac.il/report/2000/051Comments and Revisions published for TR00-051en-usFri, 14 Jul 2000 12:56:55 +0300
Paper TR00-051
| Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs and Planar Graphs |
Marek Karpinski,
Miroslaw Kowaluk,
Andrzej Lingas
https://eccc.weizmann.ac.il/report/2000/051The max-bisection problem is to find a partition of the vertices of a
graph into two equal size subsets that maximizes the number of edges with
endpoints in both subsets.
We obtain new improved approximation ratios for the max-bisection problem on
the low degree $k$-regular graphs for $3\le k\le 8,$ by deriving some improved
transformations from a maximum cut into a maximum bisection partition. In the
case 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 the
max-bisection problem for planar graphs of a sublinear degree.
Fri, 14 Jul 2000 12:56:55 +0300https://eccc.weizmann.ac.il/report/2000/051