Atenção: Todas as denúncias são sigilosas e sua identidade será preservada.
Os campos nome e e-mail são de preenchimento opcional
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.creator | Cavique, Luís | - |
Autor(es): dc.creator | Luz, Carlos J. | - |
Data de aceite: dc.date.accessioned | 2019-08-21T16:56:21Z | - |
Data de disponibilização: dc.date.available | 2019-08-21T16:56:21Z | - |
Data de envio: dc.date.issued | 2011-10-19 | - |
Data de envio: dc.date.issued | 2011-10-19 | - |
Data de envio: dc.date.issued | 2009 | - |
Fonte completa do material: dc.identifier | http://hdl.handle.net/10400.2/1901 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/10400.2/1901 | - |
Descrição: dc.description | 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. | - |
Idioma: dc.language | en | - |
Publicador: dc.publisher | Springer New York | - |
Relação: dc.relation | DOI: 10.1007/s10958-009-9613-x | - |
Direitos: dc.rights | openAccess | - |
Palavras-chave: dc.subject | Stability number ofa graph | - |
Palavras-chave: dc.subject | Convex quadratic programming | - |
Palavras-chave: dc.subject | Tabu search | - |
Título: dc.title | A heuristic for the stability number of a graph based on convex quadratic programming and tabu search | - |
Tipo de arquivo: dc.type | livro digital | - |
Aparece nas coleções: | Repositório Aberto - Universidade Aberta (Portugal) |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: