Maximum matching by convex quadratic programming based o an adverse graph conje...

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

Description

In this talk, we describe a procedure for determining a maximum stable set in a graph with convex-$QP$ stability number (which is a graph whose stability number can be determined by solving a convex quadratic programming problem) unless there is a subgraph for which neither the optimal value of the convex quadratic program nor the least adjacency eigenvalue changes when the neighborhood of any vertex is deleted. Such a graph is called adverse. Assuming the trueness of the adverse graph conjecture (which states 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 a maximum matching. With this procedure, we decide if a graph has or not convex-$QP$ stability number or a counterexample for the conjecture is determined. So far, from our computations, no counterexample was found and we believe that this conjecture is true.