Convex quadratic programming applied to the stability number of a graph

• Author(s): Pacheco, Maria F. ; Cardoso, Domingos Moreira ; Luz, Carlos J.
• Date: 2012
• Persistent ID: http://hdl.handle.net/10198/10653
• Origin: Biblioteca Digital do IPB
• Subject(s): Stability number; Convex quadratic programming; Maximum matching
• Document Type: Conference Object
• Language: Portuguese

Description

We deal with graphs whose stability number can be determined by a convex quadratic program and describe algorithmic techniques for the determination of maximum stabe sets in such graphs (except there is an induced subgraph with least adjacency eigenvalue and optimal value of the convex quadratic program not changing if the neighbourhood of any vertex is deleted). Such a graph is called adverse. Assuming that every adverse graph has convex-QP stability number, an algorithm for the recognition of graphs with convex-QP stability number is introduced and applied to the determination of maximum matchings.