Repositório Institucional da Universidade de Aveiro > Departamento de Matemática > MAT - Artigos >
 A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph
Please use this identifier to cite or link to this item http://hdl.handle.net/10773/4316

title: A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph
authors: Luz, C. J.
Cardoso, Domingos M.
keywords: Combinatorial optimization
Graph theory
Maximum independent set
Quadratic programming
issue date: 1998
publisher: Springer Verlag
abstract: A family of quadratic programming problems whose optimal values are upper bounds on the independence number of a graph is introduced. Among this family, the quadratic programming problem which gives the best upper bound is identified. Also the proof that the upper bound introduced by Hoffman and Lovász for regular graphs is a particular case of this family is given. In addition, some new results characterizing the class of graphs for which the independence number attains the optimal value of the above best upper bound are given. Finally a polynomial-time algorithm for approximating the size of the maximum independent set of an arbitrary graph is described and the computational experiments carried out on 36 DIMACS clique benchmark instances are reported.
URI: http://hdl.handle.net/10773/4316
ISSN: 0254-5330
publisher version/DOI: http://www.springerlink.com/content/q77h145367453152/
source: Annals of Operations Research
appears in collectionsMAT - Artigos

files in this item

file description sizeformat
AnnalsOR-LuzCardoso98.pdfElectronic Version120.48 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