Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/4315
Title: | A quadratic programming approach to the determination of an upper bound on the weighted stability number |
Author: | Luz, C.J. Cardoso, D.M. |
Keywords: | Graph theory Quadratic programming Weighted stability number Computational methods Decision making Decision theory Heuristic methods Problem solving Weighted stability numbers Operations research |
Issue Date: | 2001 |
Publisher: | Elsevier |
Abstract: | 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 |
Publisher Version: | http://www.sciencedirect.com/science/article/pii/S0377221700001624 |
Appears in Collections: | DMat - Artigos |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
EJOR-LuzCardoso2001pdf.pdf | Electronic Version | 151.68 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.