Graph Partitioning and Continuous Quadratic Programming
Graph Partitioning and Continuous Quadratic Programming
复制标题
DOI：
10.1137/s0895480199335829
复制
发表时间：
1999-10
期刊：
影响因子：
--
通讯作者：
W. Hager;Y. Krylyuk
中科院分区：
文献类型：
--
作者：
W. Hager;Y. Krylyuk
给出了最小割图划分问题的一个连续二次规划公式。在这些问题中，我们将图的顶点划分为满足指定大小约束的不相交集合的集合，同时最小化连接不同集合中顶点的边的权重之和。最优解与对应于图的拉普拉斯算子的第二小特征值的特征向量（Fiedler向量）相关。给出了二次规划局部极小的充要条件。对角扰动的局部极小的数量的影响进行了研究，使用文献中的测试问题。
A continuous quadratic programming formulation is given for min-cut graph partitioning problems. In these problems, we partition the vertices of a graph into a collection of disjoint sets satisfying specified size constraints, while minimizing the sum of weights of edges connecting vertices in different 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 quadratic program are given. The effect of diagonal perturbations on the number of local minimizers is investigated using a test problem from the literature.