A generalization of the Hoffman - Lovász upper boundon the independence number of a regular graph

Carlos Luz and Domingos Cardoso

Annals of Operations Research, 1998, vol. 81, issue 0, 307-320

Abstract: A family of quadratic programming problems whose optimal values are upper boundson the independence number of a graph is introduced. Among this family, the quadraticprogramming problem which gives the best upper bound is identified. Also the proof thatthe upper bound introduced by Hoffman and Lovász for regular graphs is a particular caseof this family is given. In addition, some new results characterizing the class of graphs forwhich the independence number attains the optimal value of the above best upper bound aregiven. Finally a polynomial-time algorithm for approximating the size of the maximumindependent set of an arbitrary graph is described and the computational experiments carriedout on 36 DIMACS clique benchmark instances are reported. Copyright Kluwer Academic Publishers 1998

Date: 1998
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018965309522 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:81:y:1998:i:0:p:307-320:10.1023/a:1018965309522

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018965309522

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().