Graph Partitioning and Continuous Quadratic Programming

Autor:	William W. Hager, Yaroslav Krylyuk
Rok vydání:	1999
Předmět:	Discrete mathematics General Mathematics MathematicsofComputing_NUMERICALANALYSIS Graph partition Strength of a graph Hypercube graph Combinatorics Graph power Cycle graph Path graph Null graph Complement graph MathematicsofComputing_DISCRETEMATHEMATICS Mathematics
Zdroj:	SIAM Journal on Discrete Mathematics. 12:500-523
ISSN:	1095-7146 0895-4801
DOI:	10.1137/s0895480199335829
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::c0c94393ec12757fb73f9e4fff04fcea https://doi.org/10.1137/s0895480199335829 Zobrazit plný text záznamu Plný text ve formátu PDF