Simple ingredients leading to very efficient heuristics for the maximum clique problem

• Battiti, R., Protasi, M.: Reactive local search for the maximum clique problem. Algorithmica 29(4), 610–637 (2001)

  Article  MATH  MathSciNet  Google Scholar 

• Bellare, M., Goldreich, O., Sudan, M.: Free bits, PCPs, and nonapproximability—towards tight results. SIAM J. Comput. 27(3), 804–915 (1998)

  Article  MATH  MathSciNet  Google Scholar 

• Bomze, I.M., Budinich, M., Pardalos, P.M., Pelillo, M.: The maximum clique problem. In: Du, D.Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, suppl. vol. A, pp. 1–74 (1999)

• Bomze, I.M., Pelillo, M., Stix, V.: Approximating the maximum weight clique using replicator dynamic. IEEE Trans. Neural Netw. 11(6), 1228–1241 (2000)

  Article  Google Scholar 

• Brockington, M., Culberson, J.C.: Camouflaging independent sets in quasi-random graphs, in Johnson and Trick (1996)

• Burer, S., Monteiro, R.D.C., Zhang, Y.: Maximum stable set formulations and heuristics based on continuous optimization. Math. Prog. 94, 137–166 (2002)

  Article  MATH  MathSciNet  Google Scholar 

• Busygin, S.: A new trust region technique for the maximum clique problem. Discrete Appl. Math. 154, 2080–2096 (2006)

  Article  MATH  MathSciNet  Google Scholar 

• de Klerk, E., Pasechnik, D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12, 875–892 (2002)

  Article  MATH  MathSciNet  Google Scholar 

• Dukanovic, I., Rendl, F.: Semidefinite programming relaxations for graph coloring and maximal clique problems. Working paper, Univ. of Klagenfurt, available at http://www.optimization-online.org/DB_HTML/2005/03/1081.html (2005)

• Fahle, T.: Simple and fast: improving a branch-and-bound algorithm for maximum clique. LNCS, vol. 2461, pp. 485–498 (2002)

• Garey, M., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Wiley, New York (1977)

  Google Scholar 

• Grosso, A., Locatelli, M., Della Croce, F.: Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem. J. Heuristics 10, 135–152 (2004)

  Article  Google Scholar 

• Grosso, A., Locatelli, M., Pullan, W.J.: Short communication, larger cliques for a DIMACS test. http://www.optimization-online.org/DB_HTML/2005/02/1054.html (2005)

• Gvozdenovic̀, N., Laurent, M.: Semidefinite bounds for the stability number of a graph via sums of squares of polynomials. In: Integer Programming and Combinatorial Optimization: 11th International IPCO Conference. Lecture Notes in Computer Science, vols. 3509/2005, pp. 136–151. (2005)

• Hansen, P., Mladenović, N., Urošević, D.: Variable neighborhood search for the maximum clique. Discrete Appl. Math. 145, 117–125 (2004)

  Article  MATH  MathSciNet  Google Scholar 

• Jagota, A., Sanchis, L.A.: Adaptive, restart, randomized greedy heuristics for maximum clique. J. Heuristics 7, 565–585 (2001)

  Article  MATH  Google Scholar 

• Johnson, D.S., Trick, M. (eds.): Cliques, Coloring and Satisfiability: Second DIMACS Implementation Challenge. DIMACS Series, vol. 26. American Mathematical Society, Providence (1996)

  MATH  Google Scholar 

• Katayama, K., Hamamoto, A., Narihisa, H.: An effective local search for the maximum clique problem. Inform. Process. Lett. 95, 503–511 (2005)

  Article  MathSciNet  Google Scholar 

• Östergard, P.R.J.: A fast algorithm for the maximum clique problem. Discrete Appl. Math. 120, 197–207 (2002)

  Article  MATH  MathSciNet  Google Scholar 

• Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 796–817 (2001)

  Article  MATH  MathSciNet  Google Scholar 

• Massaro, A., Pelillo, M., Bomze, I.M.: A complementary pivoting approach to the maximum weight clique problem. SIAM J. Optim 12(4), 928–948 (2002)

  Article  MATH  MathSciNet  Google Scholar 

• Pena, J., Vera, J., Zuluaga, L.: Computing the stability number of a graph via linear and semidefinite programming. Working Paper, Tepper School of Business, Carnegie Mellon Univ., available at http://www.optimization-online.org/DB_HTML/2005/04/1106.html (2005)

• Pullan, W.J., Hoos, H.H.: Dynamic local search for the maximum clique problem. J. Artif. Intell. Res. 25, 159–185 (2006)

  MATH  Google Scholar 

• Regin, J.-C.: Solving the maximum clique problem with constraint programming. In: LNCS, vol. 2883, pp. 634–648 (2003)

• Sanchis, L., Jagota, A.: Some experimental and theoretical results on test case generators for the maximum clique problem. INFORMS J. Comput. 8(2), 87–102 (1996)

  Article  MATH  Google Scholar 

• SAT’04 Competition, http://www.lri.fr/~simon/contest04/results/ (2004)

• Schrijver, A.: A comparison of the Delsarte and Lovasz bounds. IEEE Trans. Inform. Theory 25, 425–429 (1979)

  Article  MATH  MathSciNet  Google Scholar 

• Shinano, Y., Fujie, T., Ikebe, Y., Hirabayashi, R.: Solving the maximum clique problem using PUBB. In: Proceedings 12th IPPS/ 9th SPDP, pp. 326–332 (1998)

• Singh, A., Gupta, A.K.: A hybrid heuristics for the maximum clique problem. J. Heuristics 12, 5–22 (2006)

  Article  MATH  Google Scholar 

• Solnon, C., Fenet, S.: A study of ACO capabilities for solving the maximum clique problem. J. Heuristics 12, 155–180 (2006)

  Article  MATH  Google Scholar 

• Wood, D.R.: An algorithm for finding a maximum clique in a graph. Oper. Res. Lett. 21(5), 211–217 (1997)

  Article  MATH  MathSciNet  Google Scholar 

Download references