| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 959.86 KB | Adobe PDF |
Advisor(s)
Abstract(s)
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.
Description
Keywords
Maximum matching Convex quadratic programming
Citation
Pacheco, Maria F.; Cardoso, Domingos Moreira; Luz, Carlos J. (2012). Maximum matching by convex quadratic programming based o an adverse graph conjecture. In ECCO XXV - 25th Conference of Eurepean Chapter of Operational Research. Antalya, Turkey