Repositório Institucional da Universidade de Aveiro > Departamento de Matemática > MAT - Artigos >
 A quadratic programming approach to the determination of an upper bound on the weighted stability number
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
authors: 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.
URI: http://hdl.handle.net/10773/4315
ISSN: 0377-2217
publisher version/DOI: http://www.sciencedirect.com/science/article/pii/S0377221700001624
source: European Journal of Operational Research
appears in collectionsMAT - Artigos

files in this item

file description sizeformat
EJOR-LuzCardoso2001pdf.pdfElectronic Version151.68 kBAdobe PDFview/open
Restrict Access. You can Request a copy!

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! RCAAP OpenAIRE DeGóis
ria-repositorio@ua.pt - Copyright ©   Universidade de Aveiro - RIA Statistics - Powered by MIT's DSpace software, Version 1.6.2