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

Cavique, Luís; Luz, Carlos J.

http://hdl.handle.net/10400.2/1901

Use this identifier to reference this record.

Name:	Description:	Size:	Format:
2009 Lcv & Luz.pdf		241.46 KB	Adobe PDF	Download

Send Feedback

Authors

Cavique, Luís

Luz, Carlos J.

Abstract(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.

Keywords

Stability number ofa graph Convex quadratic programming Tabu search

URI

http://hdl.handle.net/10400.2/1901

Citation

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