Skip to main content

Advertisement

SpringerLink
Log in

A hybrid heuristic for the maximum clique problem

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

In this paper we present a heuristic based steady-state genetic algorithm for the maximum clique problem. The steady-state genetic algorithm generates cliques, which are then extended into maximal cliques by the heuristic. We compare our algorithm with three best evolutionary approaches and the overall best approach, which is non-evolutionary, for the maximum clique problem and find that our algorithm outperforms all the three evolutionary approaches in terms of best and average clique sizes found on majority of DIMACS benchmark instances. However, the obtained results are much inferior to those obtained with the best approach for the maximum clique problem.

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

  • Abello, J., P.M. Pardalos, and M.G.C. Resende. (2000). “On Maximum Clique Problem in Very Large Graphs.” DIMACS Series in Discrete Mathematics and Theoretical Computer Science 50, 119–130.

    MathSciNet  Google Scholar 

  • Aggarwal, C.C., J.B. Orlin, and R.P. Tai. (1997). “An Optimized Crossover for Maximum Independent Set.”Operations Research 45, 226–234.

    MathSciNet  Google Scholar 

  • Balas, E. and W. Niehaus. (1996). “Finding Large Cliques in Arbitrary Graphs by Bipartite Matching.” DIMACS Series in Discrete Mathematics and Computer Science 26, 29–51.

    MathSciNet  Google Scholar 

  • Balas, E. and W. Niehaus. (1998). “Optimized Crossover-Based Genetic Algorithms for the Maximum Cardinality and Maximum Weight Clique Problem.” Journal of Heuristics 4, 107–122.

    Article  Google Scholar 

  • Battiti, R. and M. Protasi. (2001). “Reactive Local Search for the Maximum Clique Problem.” Algorithmica 29 (4), 610–637.

    Article  MathSciNet  Google Scholar 

  • Beasley, J.E. and P.C. Chu. (1996). ”A Genetic Algorithm for the Set Covering Problem.” European Journal of Operation Research 94 (2), 394–404.

    Google Scholar 

  • Biggs, N. (1990). ”Some Heuristics for Graph Coloring.” R. Nelson and R.J. Wilson (eds.), In Graph Colourings pp. 87–96, NY: Longman.

  • Bomze, I.M., M. Budinich, P. M. Pardalos and M. Pelilo. (1999). “The Maximum Clique Problem.” Handbook of Combinatorial Optimization, 4, Boston, MA: Kluwer Academic Publishers.

  • Busygin, S. (2002). “A New Trust Region Technique for the Maximum Weight Clique Problem.” submitted to the special issue of Discrete and Applied Mathematics on Combinatorial Optimization.

  • Carraghan, R. and P.M. Pardalos. (1990). “An Exact Algorithm for the Maximum Clique Problem.” Operation. Research Letters 9, 375–382.

    Google Scholar 

  • Davis, L. (1991). Handbook of Genetic Algorithms, New York: Van Nostrand Reinhold.

    Google Scholar 

  • Dorigo, M. and T. Stutzle. (2004). Ant Colony Optimization.MIT Press/Bradford Books.

  • Fenet, S. and C. Solnon, (2003). “Searching for Maximum Clique with Ant Colony Optimization.” Applications of Evolutionary Computing (EvoCOP 2003), LNCS 2611, Springer-Verlag, pp. 236–246.

  • Feo, T.A., M.G.C. Resende, and S.M. Smith. (1994). “A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set.” Operations Research 46(5), 860–878.

    Google Scholar 

  • Garey, M.R. and D.S. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman.

    Google Scholar 

  • Grosso, A., M. Locatelli, and F. Della Croce. (2004). “Combining Swaps and Node Weights in an Adaptive Greedy Approach for the Maximum Clique Problem.” Journal of Heuristics 10, 135–152.

    Article  Google Scholar 

  • Homer, S. and M. Peinado. (1996). ”On the Performance of Polynomial Time Clique Approximation Algorithms on Very Large Graphs” Clique, Coloring and Satisfiability, Second DIMACS Implementation Challenge, pp. 221–242 D. S. Johnson and M. A. Trick (eds.).

  • Jagota, A. and L.A. Sanchis. (2001). “Adaptive, Restart, Randomized Greedy Heuristics for Maximum Clique.” Journal of Heuristics 7, 565–585.

    Article  Google Scholar 

  • Johnson, D.S. (1974). “Approximation Algorithms for Combinatorial Problems.” Journal of Computer Science 9, 256–278.

    MATH  Google Scholar 

  • Khot, S. (2001). “Improved Inapproximability Results for Maxclique, Chromatic Number and Approximate Graph Coloring.” In Proceedings of 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 600–609.

  • Marchiori, E. (2002). “Genetic, Iterated and Multistart Local Search for the Maximum Clique Problem.” Applications of Evolutionary Computing (EvoCOP 2002), LNCS 2279, Springer-Verlag, pp. 112–121.

  • Massaro, A., M. Pellilo and I. M. Bomze. (2002). “A Complementary Pivoting Approach to the Maximum Weight Clique Problem.” SIAM Journal of Optimization12, 928–948.

    Article  Google Scholar 

  • Motzkin, T.S. and E.G. Strauss. (1965). “Maxima for Graphs and a New Proof of Theorem of Turan.” Canadian Journal of Mathematics17, 533–540.

    Google Scholar 

  • Resende, M.G.C., T.A. Feo, and S.H. Smith. (1998). “Algorithm 786: FORTRAN Subroutines for Approximate Solution of the Maximum Independent Set Problem Using GRASP.” ACM Transactions on Mathematical Software24, 386–394.

    Article  Google Scholar 

  • Soriano, P. and M. Gendreau. (1996). “Tabu Search Algorithms for the Maximum Clique.” Clique, Coloring and Satisfiability, Second DIMACS Implementation Challenge, D.S. Johnson and M.A. Trick (eds.), pp. 221–242.

Download references

Author information

Authors and Affiliations

  1. J. K. Institute of Applied Physics and Technology, Faculty of Science, University of Allahabad, Allahabad, 211002, UP, India

    Alok Singh & Ashok Kumar Gupta

Authors
  1. Alok Singh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ashok Kumar Gupta
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alok Singh.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Singh, A., Gupta, A.K. A hybrid heuristic for the maximum clique problem. J Heuristics 12, 5–22 (2006). https://doi.org/10.1007/s10732-006-3750-x

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10732-006-3750-x

Keywords

Search

Navigation