  An exact algorithm is presented for solving edge weighted graph partitioning
problems. The algorithm is based on a branch and bound method applied to a
continuous quadratic programming formulation of the problem. Lower bounds are
obtained by decomposing the objective function into convex and concave parts
and replacing the concave part by an affine underestimate. It is shown that the
best affine underestimate can be expressed in terms of the center and the
radius of the smallest sphere containing the feasible set. The concave term is
obtained either by a constant diagonal shift associated with the smallest
eigenvalue of the objective function Hessian, or by a diagonal shift obtained
by solving a semidefinite programming problem. Numerical results show that the
proposed algorithm is competitive with state-of-the-art graph partitioning
codes.
