Publication
A heuristic for the stability number of a graph based on convex quadratic programming and tabu search
| dc.contributor.author | Cavique, Luís | |
| dc.contributor.author | Luz, Carlos J. | |
| dc.date.accessioned | 2011-10-19T16:53:10Z | |
| dc.date.available | 2011-10-19T16:53:10Z | |
| dc.date.issued | 2009 | |
| dc.description.abstract | 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. | por |
| dc.identifier.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 | por |
| dc.identifier.issn | ISSN: 1072-3374 (print version) | |
| dc.identifier.issn | ISSN: 1573-8795 (electronic version) | |
| dc.identifier.uri | http://hdl.handle.net/10400.2/1901 | |
| dc.language.iso | eng | por |
| dc.peerreviewed | yes | por |
| dc.publisher | Springer New York | por |
| dc.relation.publisherversion | DOI: 10.1007/s10958-009-9613-x | por |
| dc.subject | Stability number ofa graph | por |
| dc.subject | Convex quadratic programming | por |
| dc.subject | Tabu search | por |
| dc.title | A heuristic for the stability number of a graph based on convex quadratic programming and tabu search | por |
| dc.type | journal article | |
| dspace.entity.type | Publication | |
| oaire.citation.endPage | 955 | por |
| oaire.citation.issue | Journal of Mathematical Sciences, vol. 161, number 6, | por |
| oaire.citation.startPage | 944 | por |
| oaire.citation.title | Journal of Mathematical Sciences | por |
| person.familyName | Cavique | |
| person.givenName | Luís | |
| person.identifier.ciencia-id | 911E-84AC-3956 | |
| person.identifier.orcid | 0000-0002-5590-1493 | |
| rcaap.rights | openAccess | por |
| rcaap.type | article | por |
| relation.isAuthorOfPublication | 40906a16-46a2-42f1-b26d-7db7012294ee | |
| relation.isAuthorOfPublication.latestForDiscovery | 40906a16-46a2-42f1-b26d-7db7012294ee |