A heuristic for the stability number of a graph based on convex quadratic programming and tabu search

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.creatorCavique, Luís-
Autor(es): dc.creatorLuz, Carlos J.-
Data de aceite: dc.date.accessioned2019-08-21T16:56:21Z-
Data de disponibilização: dc.date.available2019-08-21T16:56:21Z-
Data de envio: dc.date.issued2011-10-19-
Data de envio: dc.date.issued2011-10-19-
Data de envio: dc.date.issued2009-
Fonte completa do material: dc.identifierhttp://hdl.handle.net/10400.2/1901-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/10400.2/1901-
Descrição: dc.descriptionRecently, 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.-
Idioma: dc.languageen-
Publicador: dc.publisherSpringer New York-
Relação: dc.relationDOI: 10.1007/s10958-009-9613-x-
Direitos: dc.rightsopenAccess-
Palavras-chave: dc.subjectStability number ofa graph-
Palavras-chave: dc.subjectConvex quadratic programming-
Palavras-chave: dc.subjectTabu search-
Título: dc.titleA heuristic for the stability number of a graph based on convex quadratic programming and tabu search-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositório Aberto - Universidade Aberta (Portugal)

Não existem arquivos associados a este item.