Skip to main content
SpringerLink
Log in

An exact algorithm for the maximum stable set problem

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

We describe a new branch-and-bound algorithm for the exact solution of the maximum cardinality stable set problem. The bounding phase is based on a variation of the standard greedy algorithm for finding a colouring of a graph. Two different node-fixing heuristics are also described. Computational tests on random and structured graphs and very large graphs corresponding to ‘real-life’ problems show that the algorithm is competitive with the fastest algorithms known so far.

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. Avis, D., A note on some computationally difficult set covering problems.Mathematical Programming, 8:138–145, 1980.

    Google Scholar 

  2. Babel, L., Finding maximum cliques in arbitrary and special graphs.Computing, 46/4:321–341, 1991.

    Google Scholar 

  3. Babel, L. and Tinhofer, G., A branch and bound algorithm for the maximum clique problem.J. of Global Optimization, 4, 1994.

  4. Balas, E. and Yu., C.S., Finding a maximum clique in an arbitrary graph.SIAM Journal on Computing, 15:1054–1068, 1986.

    Google Scholar 

  5. Bela Bollobas,Random Graphs. Academic Press, 1985.

  6. Brelaz, D., New methods to color the vertices of a graph.Comm. of the ACM, 22:251–256, 1979.

    Google Scholar 

  7. Brglez, F. and Fujiwara, H., A neutral netlist of 10 combinatorial bench-mark circuits and a target translator in fortran.Iscas'85: IEEE Int. Symp.on Circuits and Systems (Kyoto-Japan),June 1985.

  8. Calia, E. and Lioy, A., Test generation in a distributed environment. Technical report, Politecnico di Torino, C.so Duca degli Abbruzzi 24, 10129 Torino-Italy, August 1991.

    Google Scholar 

  9. Carraghan, R. and Pardalos, P.M., An exact algorithm for the maximum clique problem.Operational Research Letters 9:375–382, 1990.

    Google Scholar 

  10. Feo, T.A. and Resende, G.C., A probabilistic heuristic for a computationally difficult set covering problem.Operational Research Letters, 8:67–71, 1989.

    Google Scholar 

  11. Friden, C., Hertz, A. and de Werra, D., An exact algorithm based on tabu search for finding a maximum independent set in graph.Computers Opns. Res. 17(5):375–382, 1990.

    Google Scholar 

  12. Fulkerson, D.R., Nemhauser, G.L., and Trotter, L.E., Two computationally difficult set covering problems that arise in computing the 1-width of incidence matrices of steiner triple systems.Mathematical Programming Study, 2:72–81, 1974.

    Google Scholar 

  13. Garey, M.R. and Johnson, D.S.,Computer and Intractability: a Guide to the Theory of NP-Completeness. Freeman, New York, 1979.

    Google Scholar 

  14. Gavril, F., Algorithms for a maximum clique and a maximum independent set of a circle graph.Networks, 3:261–273, 1973.

    Google Scholar 

  15. Gavril, F., Algorithms on circular arc graphs.Networks, 4:357–369, 1974.

    Google Scholar 

  16. Grötschel, M., Lovasz, L., and Schrijver, A., Relaxation of vertex packing.J. of Comb. Theory B 40:330–343, 1986.

    Google Scholar 

  17. Gupta, U., Lee, D., and Leung, J., Efficient algorithms for interval graphs and circular arc graphs.Networks, 12:459–467, 1982.

    Google Scholar 

  18. Hasselberg, J., Pardalos, P., and Vairaktarakis, G., Test case generators and computational results for the maximum clique problem,J. of Global Optimization, 3:463–482, 1993.

    Google Scholar 

  19. Hsu, W.L., Ikura, Y., and Nemhauser, G.L., A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles.Mathematical Programming, 20:225–232, 1981.

    Google Scholar 

  20. Karmarkar, N., Resende, M., and Ramakrishnan, K., An interior point algorithm to solve computationally difficult set covering problems.Math. Prog. Series B, 52(3):597–618, 1991.

    Google Scholar 

  21. Mannino, C. and Sassano, A., An exact algorithm for the maximum stable set problem. Technical Report R.334, IASI-CNR, April 1992.

  22. Minty, G.J., On maximal independent sets of vertices in claw-free graphs.J. of Comb. Theory B, 28:284–304, 1980.

    Google Scholar 

  23. Nemhauser, G.L. and Sigismondi, G., A strong cutting plane/branch-and-bound algorithm for node packing.J. Ops. Res. Soc., 43(5):443–457, 1992.

    Google Scholar 

  24. Nemhauser, G.L. and Wolsey, L.A.,Integer and Combinatorial Optimization. John Wiley and Sons, Inc., 1988.

  25. Pardalos, P. and Xue, J., The maximum clique problem. Manuscript, August 1992.

  26. Jue Xue,Fast Algorithms for the Vertex Packing Problem. PhD thesis, Graduate School of Industrial Administration, Carnagie Mellom University, April 1991.

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Statistica, Probabilità e Statistica Applicata, Università di Roma La Sapienza, Piazzale Aldo Moro 5, 00185, Roma

    Carlo Mannino

  2. Dipartimento di Informatica e Sistemistica, Università di Roma La Sapienza, Via Buonarroti 12, 00185, Roma

    Antonio Sassano

Authors
  1. Carlo Mannino
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Antonio Sassano
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This work has been supported by Agenzia Spaziale Italiana.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Mannino, C., Sassano, A. An exact algorithm for the maximum stable set problem. Comput Optim Applic 3, 243–258 (1994). https://doi.org/10.1007/BF01299447

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01299447

Keywords

Search

Navigation