Abstract:
The 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.