DSpace
 
  Repositório Institucional da Universidade de Aveiro > Departamento de Matemática > MAT - Artigos >
 Convex Quadratic Programming Approach to the Maximum Matching Problem
Please use this identifier to cite or link to this item http://hdl.handle.net/10773/4314

title: Convex Quadratic Programming Approach to the Maximum Matching Problem
authors: Cardoso, Domingos M.
keywords: Convex programming
Graph eigenvalues
Graph theory
Maximum matching
issue date: 2001
publisher: Springer Verlag
abstract: 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.
URI: http://hdl.handle.net/10773/4314
ISSN: 0925-5001
publisher version/DOI: http://www.springerlink.com/content/hp2w356220507t55/
source: Journal of Global Optimization
appears in collectionsMAT - Artigos

files in this item

file description sizeformat
JGlobalOptimization(DCardoso2001).pdfElectronic Version284.38 kBAdobe PDFview/open
Restrict Access. You can Request a copy!
statistics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Valid XHTML 1.0! RCAAP OpenAIRE DeGóis
ria-repositorio@ua.pt - Copyright ©   Universidade de Aveiro - RIA Statistics - Powered by MIT's DSpace software, Version 1.6.2