Semidefinite programming and graph equipartition
| Author(s) : | Franz Rendl Stefan E. Karisch, |
| Publisher : | N/A |
| Publication Date : | 1998 |
| ISSN : | N/A |
| Abstract : | Abstract. Semidefinite relaxations are used to approximate the problem of partitioning a graph into equally sized components. The relaxations extend previous eigenvalue based models, and combine semidefinite and polyhedral approaches. Computational results on graphs with several hundred vertices are given, and indicate that semidefinite relaxations approximate the equipartition problem quite well. 1, |