A heuristic for the stability number of a graph based on convex quadratic programming and tabu search
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 char...
| Autor principal: | |
|---|---|
| Outros Autores: | |
| Formato: | article |
| Idioma: | eng |
| Publicado em: |
2011
|
| Assuntos: | |
| Texto completo: | http://hdl.handle.net/10400.2/1901 |
| País: | Portugal |
| Oai: | oai:repositorioaberto.uab.pt:10400.2/1901 |
| 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. |
|---|