Utilize este identificador para referenciar este registo: http://hdl.handle.net/10198/10686
Título: Maximum matching by convex quadratic programming based o an adverse graph conjecture
Autor: Pacheco, Maria F.
Cardoso, Domingos M.
Luz, Carlos J.
Palavras-chave: Maximum matching
Convex quadratic programming
Data: 2012
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.
Peer review: yes
URI: http://hdl.handle.net/10198/10686
Aparece nas colecções:ESTiG - Resumos em Proceedings Não Indexados à WoS/Scopus

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
ECC2012-abstracts.pdf959,86 kBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.