Skip to main content
SpringerLink
Log in

An Augmentation Algorithm for the Maximum Weighted Stable Set Problem

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

Abstract

Edge projection is a specialization of Lovász and Plummer's clique reduction when restricted to edges. A concept of augmenting sequences of edge-projections is defined w.r.t. a stable set S. It is then proved the equivalence between the optimality of S and the existence of an augmenting sequence w.r.t. S. This result is then exploited to develop a new tabu-search heuristic for the Maximum Stable Set Problem (weighted and unweighted). The resulting code proved to be competitive with the best codes presented in the literature.

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. L. Babel, “Finding maximum cliques in arbitrary and special graphs,” Computing, vol. 46,no. 4, pp. 321-341, 1991.

    Google Scholar 

  2. L. Babel, “A fast algorithm for the maximum weight clique problem,” Computing, vol. 52, pp. 31-38, 1994.

    Google Scholar 

  3. L. Babel and G. Tinhofer, “A branch and bound algorithm for the maximum clique problem,” ZOR-Methods and Models of Operations Research, vol. 34, pp. 207-217, 1990.

    Google Scholar 

  4. E. Balas and W. Niehaus, “Finding large clique in arbitrary graphs by bipartite matching,” in Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, D.S. Johnson and M.A. Trick (Eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26, pp. 29-51, American Mathematical Society, 1996.

  5. E. Balas and J. Xue, “Minimum weighted coloring of triangulated graphs, with application to maximum weight vertex packing and clique finding in arbitrary graphs,” SIAM Journal on Computing, vol. 20, pp. 209-221, 1991.

    Google Scholar 

  6. E. Balas and J. Xue, “Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring.” Algorithmica, vol. 15, pp. 397-412, 1996.

    Google Scholar 

  7. E. Balas and C.S. Yu, “Finding a maximum clique in an arbitrary graph,” SIAM Journal on Computing, vol. 15, pp. 1054-1068, 1986.

    Google Scholar 

  8. R. Battiti and G. Tecchiolli, “The reactive tabu search,” ORSA Journal on Computing, vol. 6,no. 2, pp. 126-140, 1994.

    Google Scholar 

  9. J. Bourjolly, G. Laporte, and H. Mercure, “A combinatorial column generation algorithm for the maximum clique and stable set problem,” Technical Report G-94-33, Les Cahiers du GERD, July 1994.

  10. M. Brockington and J.C. Culberson, “Camuflating independent sets in quasi-random graphs,” in Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, D.S. Johnson and M.A. Trick (Eds.), Discrete Mathematics and Theoretical Computer Science, vol. 26, pp. 221-242, American Mathematical Society, 1996.

  11. R. Carraghan and P.M. Pardalos, “An exact algorithm for the maximum clique problem,” Operations Research Letters, vol. 9, pp. 375-382, 1990.

    Google Scholar 

  12. C. Friden, A. Hertz, and D. de Werra, “Stabulus: a technique for finding stable sets in large graphs with tabu search,” Computing, vol. 42, pp. 35-45, 1989.

    Google Scholar 

  13. C. Friden, A. Hertz, and D. de Werra, “An exact algoritithm based on tabu search for finding a maximum independent set in graph,” Computers Opns. Res., vol. 17,no. 5, pp. 375-382, 1990.

    Google Scholar 

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

    Google Scholar 

  15. M. Gendrau and P. Soriano, “Tabu search algorithms for the maximum clique problem,” in Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, D.S. Johnson and M.A. Trick (Eds.), Discrete Mathematics and Theoretical Computer Science, vol. 26, pp. 221-242, American Mathematical Society, 1996.

  16. L.E. Gibbons, D.W. Hearn, and P.M. Pardalos, “A continuous based heuristic for the maximum clique problem,” in Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, D.S. Johnson and M.A. Trick (Eds.), Discrete Mathematics and Theoretical Computer Science, vol. 26, pp. 103-124, American Mathematical Society, 1996.

  17. F. Glover, “Future paths for integer programming and links to artificial intelligence,” Computers Opns. Res., vol. 13, pp. 533-549, 1986.

    Google Scholar 

  18. M.K. Goldberg and R.D. Rivenburgh, “Constructing cliques using restricted backtracking,” in Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, D.S. Johnson and M.A. Trick (Eds.), Discrete Mathematics and Theoretical Computer Science, vol. 26, pp. 285-307, American Mathematical Society, 1996.

  19. T. Grossman, “Applying the inn model to the max clique problem,” in Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, D.S. Johnson and M.A. Trick (Eds.), Discrete Mathematics and Theoretical Computer Science, vol. 26, pp. 125-145, American Mathematical Society, 1996.

  20. S. Homer and M. Peinado, “Experiments with polynomial-time clique approximation algorithms on very large graphs,” in Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, D.S. Johnson and M.A. Trick (Eds.), Discrete Mathematics and Theoretical Computer Science, vol. 26, pp. 147-167, American Mathematical Society, 1996.

  21. A. Jagota, L. Sanchis, and R. Ganesan, “Approximately solving maximum clique using neural network and related heuristic,” in Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, D.S. Johnson and M.A. Trick (Eds.), Discrete Mathematics and Theoretical Computer Science, vol. 26, pp. 169-204, American Mathematical Society, 1996.

  22. L. Lovász and M.D. Plummer, Matching Theory, North-Holland: Amsterdam, 1986.

    Google Scholar 

  23. C. Mannino and A. Sassano, “An exact algorithm for the maximum stable set problem,” J. Computational Optimization and Applications, vol. 3, pp. 243-258, 1994.

    Google Scholar 

  24. C. Mannino and A. Sassano, “Edge projection and the maximum stable set problem,” in Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, D.S. Johnson and M.A. Trick (Eds.), Discrete Mathematics and Theoretical Computer Science, vol. 26, pp. 205-219, American Mathematical Society, 1996.

  25. G.L. Nemhauser and G. Sigismondi, “A strong cutting plane/branch-and-bound algorithm for node packing,” J. Ops. Res. Soc., vol. 43,no. 5, pp. 443-457, 1992.

    Google Scholar 

  26. L. Orlandani, “Algoritmi di ricerca tabù per il problema del maxclique,” Master's Thesis, Dipartimento di Matematica, Facoltà di Scienze Matematiche, Fisiche e Naturali, Via della Ricerca Scientifica, 00133 Rome, Italy, 1994.

    Google Scholar 

  27. P. Pardalos and J. Xue, “The maximum clique problem,” J. of Global Optimization, vol. 4,no. 3, pp. 286-301, 1994.

    Google Scholar 

  28. E.C. Sewell, “A branch and bound algorithm for the stability number of a sparse graph,” INFORMS J. on Comp., May 1995, to appear.

  29. C. De Simone and A. Sassano, “Stability number of bull and chair-free graphs,” Discrete Applied Mathematics, vol. 41, pp. 121-129, 1993.

    Google Scholar 

  30. Jue Xue, “Fast algorithms for the vertex packing problem,” Ph.D. Thesis, Graduate School of Industrial Administration, Carnegie Mellon University, April 1991.

Download references

Author information

Authors and Affiliations

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

    Carlo Mannino & Egidio Stefanutti

Authors
  1. Carlo Mannino
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Egidio Stefanutti
    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

Mannino, C., Stefanutti, E. An Augmentation Algorithm for the Maximum Weighted Stable Set Problem. Computational Optimization and Applications 14, 367–381 (1999). https://doi.org/10.1023/A:1026456624746

Download citation

  • Issue Date:

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

Search

Navigation