Utilize este identificador para referenciar este registo:
|Título:||Maximum matching by convex quadratic programming based o an adverse graph conjecture|
|Autor:||Pacheco, Maria F.|
Cardoso, Domingos Moreira
Luz, Carlos J.
Convex quadratic programming
|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|
|Resumo:||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.|
|Aparece nas colecções:||DEMAT - Resumos em Proceedings Não Indexados ao ISI/Scopus|
Ficheiros deste registo:
|ECC2012-abstracts.pdf||959,86 kB||Adobe PDF||Ver/Abrir|
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.