Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10773/4315
Título: | A quadratic programming approach to the determination of an upper bound on the weighted stability number |
Autor: | Luz, C.J. Cardoso, D.M. |
Palavras-chave: | Graph theory Quadratic programming Weighted stability number Computational methods Decision making Decision theory Heuristic methods Problem solving Weighted stability numbers Operations research |
Data: | 2001 |
Editora: | Elsevier |
Resumo: | In a previous work, the authors have introduced an upper bound on the stability number of a graph and several of its properties were given. The determination of this upper bound was done by a quadratic programming approach whose implementation has given good computational results. We now extend this bound to the weighted case, i.e., an upper bound on the weighted stability of an arbitrary graph with node weights is presented. Similarly to the non-weighted case, the deduced bound allows us to give a necessary and sufficient condition to a weighted graph that attains the given bound. Also a heuristic for determining the maximum weight stable set is proposed which is based on an integrality property of a convex quadratic problem that produces the bound. Some comments about the proposed approach will conclude the paper. © 2001 Elsevier Science B.V. |
Peer review: | yes |
URI: | http://hdl.handle.net/10773/4315 |
ISSN: | 0377-2217 |
Versão do Editor: | http://www.sciencedirect.com/science/article/pii/S0377221700001624 |
Aparece nas coleções: | DMat - Artigos |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
EJOR-LuzCardoso2001pdf.pdf | Electronic Version | 151.68 kB | Adobe PDF |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.