Convex quadratic programming approach

作     者：Cardoso, DM 

作者机构：Univ Aveiro Dept Matemat P-3810139 Aveiro Portugal 

出 版 物：《JOURNAL OF GLOBAL OPTIMIZATION》 (全局最优化杂志)

年 卷 期：2001年第19卷第3期

页      面：291-306页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：UI&D “Matemática e Aplicações” of Math’s Department of Aveiro University 

主　　题：convex programming graph theory maximum matching graph eigenvalues 

摘      要：The problem of determining a maximum matching or whether there exists a perfect matching, is very common in a large variety of applications and as been extensively studied in graph theory. In this paper we start to introduce a characterisation of a family of graphs for which its stability number is determined by convex quadratic programming. The main results connected with the recognition of this family of graphs are also introduced. It follows a necessary and sufficient condition which characterise a graph with a perfect matching and an algorithmic strategy, based on the determination of the stability number of line graphs, by convex quadratic programming, applied to the determination of a perfect matching. A numerical example for the recognition of graphs with a perfect matching is described. Finally, the above algorithmic strategy is extended to the determination of a maximum matching of an arbitrary graph and some related results are presented.