An Investigation of the MaxCut Problem

The MaxCut problem seeks to partition the vertices of a graph into two sets such that the weight of the edges joining those sets is maximized. The MaxCut problem has been of continued research interest and has developed an extensive literature. After reviewing of a small portion of that literature, this article discusses an approach to the solution of this problem based on a branch and bound algorithm composed with a divide and conquer preprocessing phase. Preliminary results are given and several directions for further research are outlined