Algorithms for graph partitioning problems by means of eigenspace relaxations (Q1577115)

The authors investigate the problem of partitioning an edge weighted graph into \(k\) connected components so as to minimize the weight of the edges between components. They propose an algorithm for the problem based on eigenvalue methods. The connection between this problem and semi-definite optimization and eigenvalue bounds is well known and therefore the performance of algorithms based on such bounds is of current interest. This paper uses the Donath-Hoffman bound (which is computed by a subgradient algorithm) and a variant of an algorithm by Boppana. Computational results are provided.