Skip to main content
SpringerLink
Log in

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

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. J.-M. Bourjolly, G. Laporte and H. Mercure, A combinatorial column generation algorithm for the maximum clique and stable set problems, Les Chahiers du GERAD, G-94-33 (July, 1994).

  2. D. Cvetkovic, M. Doob and H. Sachs, Spectra of Graphs, Theory and Applications, VEB Deutscher Verlag der Wissenschaften, Berlin, 1979.

    Google Scholar 

  3. M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer, Berlin, 1988.

    Google Scholar 

  4. J. Hasselberg, P. Pardalos and G. Vairaiktarakis, Test case generators and computational results for the maximum clique problem, Journal of Global Optimization 3(1993)463–482.

    Article  Google Scholar 

  5. J.J. JÚdice and A.M. Faustino, An implementation of Keller's method for two concave optimization problems, Investigação Operacional 10(2)(1990)95–109.

    Google Scholar 

  6. L. Lovász, On the Shannon capacity of a graph, IEEE Transactions on Information Theory 25(2) (1979)1–7.

    Article  Google Scholar 

  7. C.J. Luz, An upper bound on the independence number of a graph computable in polynomial-time, Operations Research Letters 18(1995)139–145.

    Article  Google Scholar 

  8. P.M. Pardalos and J.B. Rosen, Constrained Global Optimization: Algorithms and Applications, Lecture Notes in Computer Sciences 268, Springer, Berlin, 1987.

    Google Scholar 

  9. P.M. Pardalos and J. Xue, The maximum clique problem, Journal of Global Optimization 4(1994)301 –328.

    Article  Google Scholar 

  10. A.L. Peressini, F.E. Sullivan and J.J. Uhl, The Mathematics of Nonlinear Programming, Springer, Berlin, 1993.

    Google Scholar 

  11. G. Sewell, Computational Methods of Linear Algebra, Ellis Horwood, London, 1990.

    Google Scholar 

Download references

Authors
  1. Carlos J. Luz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Domingos M. Cardoso
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Luz, C.J., Cardoso, D.M. A generalization of the Hoffman - Lovász upper boundon the independence number of a regular graph. Annals of Operations Research 81, 307–320 (1998). https://doi.org/10.1023/A:1018965309522

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1018965309522

Keywords

Search

Navigation