Graph partitioning and continuous quadratic programming

Citation
Ww. Hager et Y. Krylyuk, Graph partitioning and continuous quadratic programming, SIAM J DISC, 12(4), 1999, pp. 500-523
Citations number
45
Categorie Soggetti
Engineering Mathematics
Journal title
SIAM JOURNAL ON DISCRETE MATHEMATICS
ISSN journal
08954801 → ACNP
Volume
12
Issue
4
Year of publication
1999
Pages
500 - 523
Database
ISI
SICI code
0895-4801(1999)12:4<500:GPACQP>2.0.ZU;2-D
Abstract
A continuous quadratic programming formulation is given for min-cut graph p artitioning problems. In these problems, we partition the vertices of a gra ph into a collection of disjoint sets satisfying specified size constraints , while minimizing the sum of weights of edges connecting vertices in diffe rent sets. An optimal solution is related to an eigenvector (Fiedler vector ) corresponding to the second smallest eigenvalue of the graph's Laplacian. Necessary and sufficient conditions characterizing local minima of the qua dratic program are given. The effect of diagonal perturbations on the numbe r of local minimizers is investigated using a test problem from the literat ure.