A carregar...
Publicação
A heuristic for the stability number of a graph based on convex quadratic programming and tabu search
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 241.46 KB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
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.
Descrição
Palavras-chave
Stability number ofa graph Convex quadratic programming Tabu search
Contexto Educativo
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. "Journal of Mathematical Sciences" [Em linha]. ISSN 1072-3374 (Print) 1573-8795 (Online). Vol. 161, nº 6, (2009), p. 944-955
Editora
Springer New York