Algorithms for graph partitioning problems by means of eigenspace relaxations (Q1577115)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Algorithms for graph partitioning problems by means of eigenspace relaxations |
scientific article |
Statements
Algorithms for graph partitioning problems by means of eigenspace relaxations (English)
0 references
30 August 2000
0 references
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.
0 references
graph partitioning
0 references
eigenvalues
0 references
\(k\)-cut
0 references