| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 959.86 KB | Adobe PDF |
Orientador(es)
Resumo(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.
Descrição
Palavras-chave
Maximum matching Convex quadratic programming
Contexto Educativo
Citação
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