Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.2/1901
Título: A heuristic for the stability number of a graph based on convex quadratic programming and tabu search
Autor: Cavique, Luís
Luz, Carlos J.
Palavras-chave: Stability number ofa graph
Convex quadratic programming
Tabu search
Data: 2009
Editora: Springer New York
Citação: Cavique, Luís; Luz, Carlos J. - A heuristic for the stability number of a graph based on convex quadratic programming and tabu search [Em linha]. "Journal of Mathematical Sciences". ISSN 1072-3374 (Print) 1573-8795 (Online). Vol. 161, nº 6, (2009), p. 944-955
Resumo: Recently, a characterization of the Lov´asz theta number based on convex quadratic programming was established. As a consequence of this formulation, we introduce a new upper bound on the stability number of a graph that slightly improves the theta number. Like this number, the new bound can be characterized as the minimum of a function whose values are the optimum values of convex quadratic programs. This paper is oriented mainly to the following question: how can the new bound be used to approximate the maximum stable set for large graphs? With this in mind we present a two-phase heuristic for the stability problem that begins by computing suboptimal solutions using the new bound definition. In the second phase a multi-start tabu search heuristic is implemented. The results of applying this heuristic to some DIMACS benchmark graphs are reported.
Peer review: yes
URI: http://hdl.handle.net/10400.2/1901
ISSN: ISSN: 1072-3374 (print version)
ISSN: 1573-8795 (electronic version)
Versão do Editor: DOI: 10.1007/s10958-009-9613-x
Aparece nas colecções:Ciências e Tecnologia - Artigos em revistas internacionais / Papers in international journals

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
2009 Lcv & Luz.pdf241,46 kBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

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