Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

The Maximum Clique Problem

  • Chapter
Handbook of Combinatorial Optimization

Abstract

The maximum clique problem is a classical problem in combinatorial optimization which finds important applications in different domains. In this paper we try to give a survey of results concerning algorithms, complexity, and applications of this problem, and also provide an updated bibliography. Of course, we build upon precursory works with similar goals [39, 232, 266].

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 129.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 169.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 169.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. E. Aarts and J. Korst, Simulated Annealing and Boltzmann Machines, J. Wiley & Sons, Chichester, UK, 1989.

    Google Scholar 

  2. E. Aarts and J.K. Lenstra (eds.), Local Search in Combinatorial Optimization, J. Wiley & Sons, Chichester, UK, 1997.

    Google Scholar 

  3. F. Abbattista, F. Bellifemmine and D. Dalbis, The Scout algorithm applied to the maximum clique problem, in Advances in Soft Computing—Engineering and Design, Springer, Berlin, 1998.

    Google Scholar 

  4. J. Abello, P.M. Pardalos and M.G.C. Resende, On maximum clique problems in very large graphs, in External Memory Algorithms, DI-MACS Series, AMS (J. Abello and J. Vitter, Editors ) 1999.

    Google Scholar 

  5. L.M. Adleman, Molecular computation of solutions to combinatorial optimization, Science, Vol. 266: 1021–1024, 1994.

    Article  Google Scholar 

  6. F. Alizadeh, A sublinear-time randomized parallel algorithm for the maximum clique problem in perfect graphs, in: A. Aggarwal (ed.), Discrete Algorithms, Proc. 2nd ACM-SIAM Symposium, Vol. 2: 188194, 1991.

    Google Scholar 

  7. N. Alon, U. Feige, A. Wigderson and D. Zuckerman, Derandomized graph products, Comput. Complex., Vol. 5: 60–75, 1995.

    Article  MathSciNet  MATH  Google Scholar 

  8. E.A. Akkoyunlu, The enumeration of maximal cliques of large graphs, SIAM J. Comput., Vol. 2: 1–6, 1973.

    Article  MathSciNet  MATH  Google Scholar 

  9. N. Alon, L. Babai and A. Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, J. Algorithms, Vol. 7: 567–583, 1986.

    Article  MathSciNet  MATH  Google Scholar 

  10. N. Alon, M. Krivelevich and B. Sudakov, Finding a large hidden clique in a random graph, in: Proc. SODA ‘88—Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco CA, January 2527, 1998.

    Google Scholar 

  11. A.P. Ambler, H.G. Barrow, C.M. Brown, R.M. Burstall and R.J. Popplestone, A versatile computer-controlled assembly system, in Proc. 3rd Int. J. Conf. Artif. Intell.: 298–307, 1973.

    Google Scholar 

  12. A.T. Amin and S.L. Hakimi, Upper bounds on the order of a clique of a graph, SIAM J. Appl. Math., Vol. 22: 569–573, 1972.

    Article  MathSciNet  MATH  Google Scholar 

  13. S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy, Proof verification and hardness of approximation problems, Proc. 33rd Ann. Symp. Found. Computer Sci.: 14–23, 1992.

    Google Scholar 

  14. S. Arora and S. Safra, Probabilistic checking of proofs: A new characterization of NP, Proc. 33rd Ann. Symp. Found. Computer Sci.: 2–13, 1992.

    Google Scholar 

  15. J.G. Auguston and J. Minker, An analysis of some graph theoretical cluster techniques, J. ACM, Vol. 17: 571–588, 1970.

    Article  Google Scholar 

  16. G. Ausiello, P. Crescenzi and M. Protasi, Approximation solution of NP optimization problems, Theor. Comput. Sci., Vol. 150: 1–55, 1995.

    Article  MathSciNet  MATH  Google Scholar 

  17. G. Avondo-Bodeno, Economic Applications of the Theory of Graphs, Gordon and Breach Science Publishers, New York, 1962.

    Google Scholar 

  18. S.M. Baas, M.C. Bonvanie and A.J. Verschoor, A relaxation method for the set packing problem using polyhedron characteristic, Technical Report 699, University of Twente, Netherlands, 1988.

    Google Scholar 

  19. L. Babel, Finding maximum cliques in arbitrary and in special graphs, Computing, Vol. 46: 321–341, 1991.

    Article  MathSciNet  MATH  Google Scholar 

  20. L. Babel, A fast algorithm for the maximum weight clique problem, Computing, Vol. 52: 31–38, 1994.

    Article  MathSciNet  MATH  Google Scholar 

  21. L. Babel and G. Tinhofer, A branch and bound algorithm for the maximum clique problem, ZOR-Methods and Models of Operations Research, Vol. 34: 207–217, 1990.

    MathSciNet  MATH  Google Scholar 

  22. T. Bäck and S. Khuri, An evolutionary heuristic for the maximum independent set problem, Proc. 1st IEEE Conf. Evolutionary Comput.: 531–535, 1994.

    Google Scholar 

  23. E. Balas, A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring, Discr, Appl. Math., Vol. 15: 123–134, 1986.

    MathSciNet  MATH  Google Scholar 

  24. E. Balas, S. Ceria, G. Corneujols and G. Pataki, Polyhedral methods for the maximum clique problem, in [189]: 11–28, 1996.

    Google Scholar 

  25. E. Balas, V. Chvâtal and J. Nesetril, On the maximum weight clique problem, Math. Oper. Res., Vol. 12: 522–535, 1987.

    Article  MathSciNet  MATH  Google Scholar 

  26. E. Balas and W. Niehaus, Finding large cliques in arbitrary graphs by bipartite matching, in [189]: 29–51, 1996.

    Google Scholar 

  27. E. Balas and H. Samuelsson, A Node Covering Algorithm, Naval Research Logistics Quarterly, Vol. 24: 213–233, 1977.

    MathSciNet  MATH  Google Scholar 

  28. E. Balas and P. Toth, Branch and bound methods, In: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys (Eds.), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, J. Wiley & Sons, Chichester, UK: 361–403, 1985.

    Google Scholar 

  29. 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 J. Comput., Vol. 2: 209–221, 1991. “Addendum,” SIAM J. Comput., Vol. 21: 1000, 1992.

    Google Scholar 

  30. E. Balas and J. Xue, Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring, Algorithmica Vol. 15: 397–412, 1996.

    Article  MathSciNet  MATH  Google Scholar 

  31. E. Balas and C.S. Yu, Finding a maximum clique in an arbitrary graph, SIAM J. Comput., Vol. 14: 1054–1068, 1986.

    Google Scholar 

  32. E. Balas and C.S. Yu, On graphs with polynomially solvable maximum-weight clique problem, Networks, Vol. 19: 247–253, 1989.

    MathSciNet  MATH  Google Scholar 

  33. D.H. Ballard and M. Brown, Computer Vision, Prentice-Hall, Englewood Cliffs, N.J., 1982.

    Google Scholar 

  34. D.H. Ballard, P.C. Gardner and M.A. Srinivas, Graph problems and connectionist architectures, Technical Report TR 167, Dept. Computer Science, University of Rochester, 1987

    Google Scholar 

  35. F. Barahona, A. Weintraub, and R. Epstein, Habitat dispersion in forest planning and the stable set problem, Oper. Res. Vol. 40, Supp. 1: S14 — S21, 1992.

    Google Scholar 

  36. H.G. Barrow and R.M. Burstall, Subgraph isomorphism, matching relational structures and maximal cliques, Inform. Proc. Lett., Vol. 4: 83–84, 1976.

    Article  MATH  Google Scholar 

  37. R. Battiti and M. Protasi, Reactive local search for the maximum clique problem, Technical Report TR-95–052, International Computer Science Institute, Berkeley, CA, 1995.

    Google Scholar 

  38. A.R. Bednarek and O.E. Taulbee, On maximal chains, Roum. Math. Pres et Appl., Vol. 11: 23–25, 1966.

    MathSciNet  MATH  Google Scholar 

  39. L.W. Beineke, A survey of packings and coverings in graphs, in: G. Chartrand and S. Kapoor (Eds.), Many Facets of Graph Theory, Springer: 45–53, Berlin, 1969.

    Google Scholar 

  40. M. Bellare, O. Goldreich, C. Lund and A. Russell, Efficient probabilistically checkable proofs and application to approximation, Proc. 25th Ann. ACM Symp. Theory of Comput.: 294–304, 1993.

    Google Scholar 

  41. M. Bellare, O. Goldreich and M. Sudan, Free bits, PCPs and nonapproximability—Towards tight results, SIAM J. Comput. Vol. 27: 804–915, 1997.

    Article  MathSciNet  Google Scholar 

  42. M. Bellare and M. Sudan, Improved nonapproximability results, Proc. 26th Ann. ACM Symp. Theory of Comput.: 184–193, 1994.

    Google Scholar 

  43. [43] C. Berge and V. Chvâtal (Eds.), Topics on Perfect Graphs, Ann. Discr. Math. Vol. 21, 1984.

    Google Scholar 

  44. P. Berman and A. Pelc, Distributed fault diagnosis for multiprocessor systems, Proc. of the 20th Annual Int. Symp. on Fault- Tolerant Computing (Newcastle, UK): 340–346, 1990.

    Google Scholar 

  45. P. Berman and G. Schnitger, On the complexity of approximating the independent set problem, in Proc.1989 Symposium on Theoret. Aspects of Comp. Sci., Springer, Lecture Notes in Computer Sciences Vol. 349: 256–268, Berlin, 1989.

    Google Scholar 

  46. P. Berman and G. Schnitger, On the complexity of approximating the independent set problem, Inform. and Comput., Vol. 96: 77–94, 1992.

    Article  MathSciNet  MATH  Google Scholar 

  47. A. Bertoni, P. Campadelli and G. Grossi, A discrete neural algorithm for the maximum clique problem: Analysis and circuit implementation, presented at WAE’97: Int. Workshop on Algorithm Engineering, Venice, Italy, 1997.

    Google Scholar 

  48. B.K. Bhattacharya, P. Hell and J. Huang, A linear algorithm for maximum weight cliques in proper circular arc graphs, SIAM J. Discr. Math. Vol. 9: 274–289, 1996.

    Article  MathSciNet  MATH  Google Scholar 

  49. B.K. Bhattacharya and D. Kaller, An O(m+n log n) algorithm for the maximum clique problem in circular-arc graphs, J. Algorithms Vol. 25: 33–358, 1997.

    MathSciNet  Google Scholar 

  50. D.M. Blough, Fault detection and diagnosis in multiprocessor systems Ph.D. Thesis The Johns Hopkins University1988.

    Google Scholar 

  51. R.C. Bolles and R.A. Cain, Recognizing and locating partially visible objects: The locus-feature-focus method, Int. J. Robotics Res., Vol. 1: 57–82, 1982.

    Article  Google Scholar 

  52. R.C. Bolles and P. Horaud, 3DPO: A three-dimensional part orientation system, Int. J. Robotics Res., Vol. 5: 3–26, 1986.

    Google Scholar 

  53. B. Bollobâs, Random graphs, Academic Press, New York, NY, 1985.

    MATH  Google Scholar 

  54. B. Bollobâs, Modern graph theory, Springer, New York, NY, 1998.

    Book  MATH  Google Scholar 

  55. B. Bollobâs and P. Erdös, Cliques in Random Graphs, Math. Proc. Cambridge Philos. Soc., Vol. 80: 419–427, 1976.

    Article  MathSciNet  MATH  Google Scholar 

  56. I.M. Bomze, Evolution towards the maximum clique J. Glob. Optim. Vol. 10: 143–164, 1997.

    Google Scholar 

  57. I.M. Bomze, Global escape strategies for maximizing quadratic forms over a simplex J. Global Optim. Vol. 11: 325–338, 1997.

    Google Scholar 

  58. I.M. Bomze, On standard quadratic optimization problems J. Glob. Optim. Vol. 13: 369–387, 1998.

    Google Scholar 

  59. I.M. Bomze, M. Budinich, M. Pelillo and C. Rossi, Annealed replication: A new heuristic for the maximum clique problem, submitted for publication, 1998.

    Google Scholar 

  60. I.M. Bomze and G. Danninger, A finite algorithm for solving general quadratic problems, J. Global Optim. Vol. 4: 1–16, 1994.

    Article  MathSciNet  MATH  Google Scholar 

  61. I.M. Bomze, M. Pelillo, and R. Giacomini, Evolutionary approach to the maximum clique problem: Empirical evidence on a larger scale, in Developments in Global Optimization, I.M. Bomze, T. Csendes, R. Horst, and P.M. Pardalos (eds.), Kluwer: 95–108, Dordrecht, 1997.

    Google Scholar 

  62. I.M. Bomze, M. Pelillo, and V. Stix, Approximating the Maximum Weight Clique: An Evolutionary Game Theory Approach, manuscript in preparation, 1998.

    Google Scholar 

  63. I.M. Bomze and F. Rendi, Replicator dynamics for the evolution towards the maximum clique: Variants and experiments, in: High Performance Algorithms and Software in Nonlinear Optimization, R. De Leone, A. Murlí, P.M. Pardalos and G. Toraldo (eds.), Kluwer: 53–67, Dordrecht, 1998.

    Google Scholar 

  64. I.M. Bomze and V. Stix, Genetical engineering via negative fitness: Evolutionary dynamics for global optimization, to appear in: Ann. Oper. Res. Vol. 90, 1999.

    Google Scholar 

  65. R.E. Bonner, On some clustering techniques, IBM J. Res. Develop., Vol. 8: 22–32, 1964.

    Article  MATH  Google Scholar 

  66. R. Boppana and M.M. Halldórsson, Approximating maximum independent sets by excluding subgraphs, BIT, Vol. 32: 180–196, 1992.

    Article  MathSciNet  MATH  Google Scholar 

  67. M. Boulala and J.P. Uhry, Polytope des Independants dans un Graphe Serie-Parallele, Discr. Math., Vol. 27: 225–243, 1979.

    Article  MathSciNet  MATH  Google Scholar 

  68. J.-M. Bourjolly, P. Gill, G. Laporte and H. Mercure, An exact quadratic 0–1 algorithm for the stable set problem, in [189]: 53–73, 1996.

    Google Scholar 

  69. J.-M. Bourjolly, G. Laporte and H. Mercure, A combinatorial column generation algorithm for the maximum stable set problem, Oper. Res. Lett. Vol. 20: 21–29, 1997.

    Article  MathSciNet  MATH  Google Scholar 

  70. D.P. Bovet and P. Crescenzi, Introduction to the Theory of Complexity, Prentice-Hall, Englewood Cliffs, N.J., 1994.

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  72. M. Brockington and J.C. Culberson, Camouflaging independent sets in quasi-random graphs, in [189]: 75–88, 1996.

    Google Scholar 

  73. C. Bron and J. Kerbosch, Algorithm 457: Finding all cliques of an undirected graph, Commun. ACM, Vol. 16: 575–577, 1973.

    MATH  Google Scholar 

  74. A. E. Brouwer, J. B. Shearer, N. J. A. Sloane and W. D. Smith, A new Table of constant weight codes, IEEE Trans. Inform. Theory, Vol. 36: 1334–1380, 1990.

    Article  MathSciNet  MATH  Google Scholar 

  75. M. Budinich, Bounds on the maximum clique of a graph, submitted (http://www.ts.infn.it/“mbh/MCBounds.ps.Z).

  76. M. Budinich and P. Budinich, A Clifford algebra formulation of the maximum clique problem of a graph, preprint in preparation (will be available from http: //www. t s. infn. it/’mbh/PubNN. html).

    Google Scholar 

  77. T.N. Bui and P.H. Eppley A hybrid genetic algorithm for the maximum clique problem, Proc. 6th Int. Conf. Genetic Algorithms: 478–484, 1995.

    Google Scholar 

  78. M. Burlet and J. Fonlupt, Polynomial algorithm to recognize a Meyniel graph, W.R. Pulleyblank (ed.), Progress in Combinatorial Optimization, Academic Press, Toronto: 69–99, 1984.

    Google Scholar 

  79. J.E. Burns, The maximum independent set problem for cubic planar graph, Networks, Vol. 9: 373–378, 1989

    Article  MathSciNet  Google Scholar 

  80. R. Carraghan and P.M. Pardalos, An exact algorithm for the maximum clique problem, Oper. Res. Lett., Vol. 9: 375–382, 1990.

    Article  MATH  Google Scholar 

  81. R. Carraghan and P.M. Pardalos, A parallel algorithm for the maximum weight clique problem, Technical Report CS-90–40, Dept. of Computer Science, Penn. State Univ., 1990.

    Google Scholar 

  82. B. Carter and K. Park, How good are genetic algorithms at finding large cliques: An experimental study, Technical Report BU-CS-93015, Computer Science Dept., Boston University, 1993.

    Google Scholar 

  83. M.-S. Chang, Y.-H. Chen, G.J. Chang, and J.-H. Yan, Algorithmic aspects of the generalized clique-transversal problem on chordal graphs, Discr. Appl. Math.,Vol. 66: 189–203, 1996.

    Google Scholar 

  84. R.C. Chang, On the query complexity of clique size and maximum satisfiability, J. Comput. Syst. Sci., Vol. 53: 298–313, 1996.

    Article  MATH  Google Scholar 

  85. R.C. Chang, W.I. Gasarch, C. Lund, On bounded queries and approximation, SIAM J. Comput., Vol. 26: 188–209, 1997.

    Article  MathSciNet  MATH  Google Scholar 

  86. R.C. Chang and H.S. Lee, Finding a maximum set of independent chords in a circle, Inform. Proc. Lett., Vol. 41: 99–102, 1992.

    Article  MathSciNet  MATH  Google Scholar 

  87. N. Chiba and T. Nishizeki, Arboricity and subgraph listing algorithms, SIAM J. Comput., Vol. 14: 210–223, 1985.

    Article  MathSciNet  MATH  Google Scholar 

  88. N. Chiba, T. Nishizeki and N. Saito, An approximation algorithm for the maximum independent set problem on planar graphs, SIAM. J. Comput., Vol. 11: 663–675, 1982.

    Article  MathSciNet  MATH  Google Scholar 

  89. N. Chiba, T. Nishizeki and N. Saito, An algorithm for finding a large independent set in planar graphs, Networks, Vol. 13: 247–252, 1983.

    Article  MathSciNet  MATH  Google Scholar 

  90. E. Choukhmane and J. Franco, An approximation algorithm for the maximum independent set problem in cubic planar graphs, Networks, Vol. 16: 349–356, 1986.

    Article  MathSciNet  MATH  Google Scholar 

  91. M. Chrobak and J. Naor, An efficient parallel algorithm for computing a large independent set in a planar graph, Algorithmica, Vol. 6: 80 1815, 1991.

    MathSciNet  Google Scholar 

  92. V. Chvâtal, On certain polytopes associated with graphs, J. Combin. Theory B, Vol. 18: 138–154, 1975.

    Article  MATH  Google Scholar 

  93. V. Chvâtal, Determining the stability number of a graph, SIAM J. Comput., Vol. 6: 643–662. 1977.

    Article  MathSciNet  MATH  Google Scholar 

  94. V. Chvâtal, A greedy heuristic for the set-covering problem, Math. Oper. Res., Vol. 4: 233–23, 1979.

    Article  MathSciNet  MATH  Google Scholar 

  95. V. Chvâtal, Perfectly orderable graphs, Ann. Discr. Math., Vol. 21: 63–65, 1985.

    Google Scholar 

  96. K. Corradi and S. Szabo, A combinatorial approach for Keller’s conjecture, Periodica Mathematica Hungarica, Vol. 21: 95–100, 1990.

    Article  MathSciNet  MATH  Google Scholar 

  97. P. Crescenzi, C. Fiorini and R. Silvestri, A Note on the approximation of the MAX CLIQUE problem, Inform. Process. Lett. 40: 1–5, 1991.

    Article  MathSciNet  MATH  Google Scholar 

  98. F. Della Croce and R. Tadei, A multi-KP modeling for the maximum-clique problem, Europ. J. Oper. Res., Vol. 73: 555–561, 1994.

    Article  MATH  Google Scholar 

  99. V.-D. Cung, S. Dowaji, B. Le Cun, T. Mautor and C. Roucairol, Concurrent data structures and load balancing strategies for parallel branch-and-bound/A* algorithms, in S.N. Bhatt (ed.), Parallel algorithms, 3rd DIMACS Implementation Challenge, October 17–19, 1994, AMS DIMACS Ser. Discrete Math. Theor. Comput. Sci. Vol. 30: 141–162, 1997.

    Google Scholar 

  100. D.M. Cvetkovic, M. Doob and H. Sachs, Spectra of Graphs, Academic Press, New York, NY, 1980.

    Google Scholar 

  101. E. Dahlhaus and M. Karpinski, A fast parallel algorithm for computing all maximal cliques in a graph and the related problems, in: Algorithm Theory. Proc. 1st Scand. Workshop, Halmstad/Sweden 1988. Lect. Notes Comput. Sci. Vol. 318: 139–144, 1988.

    Google Scholar 

  102. C. De Simone and A. Sassano, Stability number and bull-and chair-free graphs, Discr. Appl. Math., Vol. 41: 121–129, 1993.

    Article  MATH  Google Scholar 

  103. V. Degot and J.M. Hualde, De l’utilisation de la notion de clique en matière de typologie des populations (in French), R.A.I.R.O., Vol. 9: 5–18, 1975.

    MATH  Google Scholar 

  104. N. Deo, Graph Theory with Applications to Engineering and Computer Science, Prentice-Hall, Englewood Cliffs, NJ, 1974.

    MATH  Google Scholar 

  105. J.F. Desler and S.L. Hakimi, On finding a maximum internally stable set of a graph, Proc. of Fourth Annual Princeton Conference on Information Sciences and Systems, Vol. 4: 459–462, Princeton, NJ, 1970.

    Google Scholar 

  106. G.A. Dirac, A property of 4-chromatic graphs and some remarks on critical graphs, J. London Math. Soc., Vol. 27: 85–92, 1952.

    Article  MathSciNet  MATH  Google Scholar 

  107. G.A. Dirac, On rigid circuit graphs, Abh. Math. Sem., Univ. Hamburg, Vol. 25: 71–76, 1961.

    Article  MathSciNet  MATH  Google Scholar 

  108. P. Doreian, A note on the detection of cliques in valued graphs, Sociometry, Vol. 32: 237–242, 1969.

    Article  Google Scholar 

  109. D.-Z. Du, B. Gao and W. Wu, A special case for subset interconnection designs, Discr. Appl. Math., Vol. 78: 51–60, 1997.

    Article  MathSciNet  MATH  Google Scholar 

  110. C. Ebenegger, P.L. Hammer, and D. de Werra, Pseudo-boolean functions and stability of graphs, Ann. Discr. Math., Vol. 19: 83–98, 1984.

    Google Scholar 

  111. U. Feige, S. Goldwasser, L. Lovâsz, S. Safra, and M. Szegedy, Approximating the maximum clique is almost NP-complete, Proc. 32nd IEEE Symp. on Foundations of Computer Science: 2–12, 1991.

    Google Scholar 

  112. U. Feige, S. Goldwasser, L. Lovâsz, S. Safra, and M. Szegedy, Interactive proofs and the hardness of approximating cliques, J. ACM, Vol. 43: 268–292, 1996.

    Article  MathSciNet  MATH  Google Scholar 

  113. U. Feige and J. Kilian, Two prover protocols—Low error at affordable rates, Proc. 26th Ann. ACM Symp. Theory of Comput.: 172–183, 1994.

    Google Scholar 

  114. S. Felsner, R. Mueller and L. Wernisch, Trapezoid graphs and generalizations, geometry and algorithms, Discr. Appl. Math., Vol. 74: 13–32, 1997.

    Google Scholar 

  115. T.A. Feo, M.G.C. Resende and S.H. Smith, A greedy randomized adaptive search procedure for maximum independent set, Oper. Res., Vol. 42: 860–878, 1994.

    Article  MATH  Google Scholar 

  116. M.L. Fisher and L.A. Wolsey, On the greedy heuristic for continuous covering and packing problems, SIAM J. Alg. Discr. Meth., Vol. 3: 584–591, 1982.

    MathSciNet  MATH  Google Scholar 

  117. C. Fleurent and J.A. Ferland, Object-oriented implementation of heuristic search methods for graph coloring, maximum clique, and satisfiability, in [189]: 619–652, 1996.

    Google Scholar 

  118. J.A. Foster and T. Soule, Using genetic algorithms to find maximum cliques, Technical Report LAL 95–12, Dept. of Computer Science, U. Idaho, 1995.

    Google Scholar 

  119. A. Frank, Some polynomial algorithms for certain graphs and hyper-graphs, Proc. 5th British Combin. Conf.: 211–226, 1976.

    Google Scholar 

  120. C. Friden, A. Hertz, and D. de Werra, STABULUS: A technique for finding stable sets in large graphs with tabu search, Computing, Vol. 42: 35–44, 1989.

    MATH  Google Scholar 

  121. C. Friden, A. Hertz and M. de Werra, TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph, Comput. Oper. Res., Vol. 17: 437–445, 1990.

    Article  MATH  Google Scholar 

  122. A. Frieze, On the independence number of random graphs, Discr. Math., Vol. 81: 171–175, 1990.

    Article  MathSciNet  MATH  Google Scholar 

  123. K. Fujisawa, M. Kojima, and K. Nakata, Exploiting sparsity in primal-dual interior-point methods for semidefinite programming, Math. Programming, Vol. 79: 235–253, 1997.

    MathSciNet  MATH  Google Scholar 

  124. N. Funabiki, Y. Takefuji, and K.C. Lee, A neural network model for finding a near-maximum clique, J. Parallel Distrib. Comput., Vol. 14: 340–344, 1992.

    Article  Google Scholar 

  125. M. Carey and D. Johnson, The complexity of near-optimal coloring, J. ACM, Vol. 23: 43–49, 1976.

    Article  Google Scholar 

  126. M. Garey and D. Johnson, Computers and Intractability—A guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.

    MATH  Google Scholar 

  127. F. Gavril, Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM J. Comput., Vol. 1: 180–187, 1972.

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  129. F. Gavril, Algorithms on circular arc graphs, Networks, Vol. 4: 357369, 1974.

    Google Scholar 

  130. M. Gendreau, J.C. Picard and L. Zubieta, An efficient implicit enumeration algorithm for the maximum clique problem, A. Kurzhanski et al. (eds), Lecture Notes in Economics and Mathematical Systems, Vol. 304: 70–91, Springer, Berlin 1988.

    Google Scholar 

  131. A. Gendreau, L. Salvail, and P. Soriano, Solving the maximum clique problem using a tabu search approach, Ann. Oper. Res., Vol. 41: 385–403, 1993.

    Article  MATH  Google Scholar 

  132. L. Gerhards and W. Lindenberg, Clique detection for nondirected graphs: Two new algorithms, Computing, Vol. 21: 295–322, 1979.

    Article  MathSciNet  MATH  Google Scholar 

  133. A.M.H. Gerards and A. Schrijver, Matrices with the Edmonds-Johnson property, Combinatorica, Vol. 6: 403–417, 1986.

    Article  MathSciNet  Google Scholar 

  134. L.E. Gibbons, D.W. Hearn and P.M. Pardalos, A continuous based heuristic for the maximum clique problem, in [189]: 103–124, 1996.

    Google Scholar 

  135. L.E. Gibbons, D.W. Hearn, P.M. Pardalos, and M.V. Ramana, Continuous characterizations of the maximum clique problem, Math. Oper. Res., Vol. 22: 754–768, 1997.

    Article  MathSciNet  MATH  Google Scholar 

  136. F. Glover, Tabu search—Part I, ORSA J. Comput., Vol. 1: 190–260, 1989.

    Article  MathSciNet  MATH  Google Scholar 

  137. F. Glover, Tabu search—Part II, ORSA J. Comput., Vol. 2: 4–32, 1990.

    Article  MATH  Google Scholar 

  138. F. Glover and M. Laguna, Tabu search, in Modern Heuristic Techniques for Combinatorial Problems, C. Reeves (ed.), Blackwell, Oxford, UK: 70–141, 1993.

    Google Scholar 

  139. G.H. Godbeer, J. Lipscomb, and M. Luby, On the computational complexity of finding stable state vectors in connectionist models (Hopfield nets), Technical Report 208/88, Dept. of Computer Science, University Toronto, 1988.

    Google Scholar 

  140. M.X. Goemans, Semidefinite programming in combinatorial optimization, Math. Programming, Vol.. 79: 143–161, 1997.

    Google Scholar 

  141. D.E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, Reading, MA, 1989.

    Google Scholar 

  142. M.K. Goldberg and R.D. Rivenburgh, Constructing cliques using restricted backtracking, in [189]: 89–101, 1996.

    Google Scholar 

  143. M. Goldberg and T. Spencer, A new parallel algorithm for the maximal independent set problem, SIAM J. Comput., Vol. 18: 419–427, 1989.

    Article  MathSciNet  MATH  Google Scholar 

  144. M. Goldberg and T. Spencer, Constructing a maximal independent set in parallel, SIAM J. Discr. Math., Vol. 2: 322–328, 1989.

    Article  MathSciNet  MATH  Google Scholar 

  145. M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, NY, 1980.

    MATH  Google Scholar 

  146. M.C. Golumbic and P.L. Hammer, Stability in circular-arc-graphs, J. Algorithms, Vol. 9: 314–320, 1988.

    MathSciNet  MATH  Google Scholar 

  147. G.R. Grimmett and W.R. Pulleyblank, Random near-regular graphs and the node packing problem, Oper. Res. Lett., Vol. 4: 169–174, 1985.

    Google Scholar 

  148. T. Grossman, Applying the INN model to the max clique problem, in [189]: 125–146, 1996.

    Google Scholar 

  149. M. Grötschel, L. Lovâsz and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, Vol. 1: 169–197, 1981.

    Google Scholar 

  150. M. Grötschel, L. Lovâsz and A. Schrijver, Relaxations of vertex packing, J. Combin. Theory B, Vol. 40: 330–343, 1986.

    MATH  Google Scholar 

  151. M. Grötschel, L. Lovâsz and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, 2nd Ed., Springer, Berlin, 1993.

    Book  MATH  Google Scholar 

  152. M. Grötschel, L. Lovâsz and A. Schrijver, Polynomial algorithms for perfect graphs, Ann. Discr. Math., Vol. 21: 325–356, 1989.

    Google Scholar 

  153. U.I. Gupta, D.T. Lee and J.Y.T. Leung, Efficient algorithms for interval graphs and circular-arc graphs, Networks, Vol. 12: 459–467, 1982.

    MathSciNet  MATH  Google Scholar 

  154. G. Hajós, Sur la factorisation des abeliens, Casopis Vol. 74: 189–196, 1950.

    Google Scholar 

  155. M.-H. Han and D. Jang, The use of maximum curvature points for the recognition of partially occluded objects, Pattern Recognition, Vol. 23: 21–33, 1990.

    Google Scholar 

  156. P. Hansen and B. Jaumard, Algorithms for the maximum satisfiability problem, Computing, Vol. 44: 279–303, 1990.

    MathSciNet  MATH  Google Scholar 

  157. F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.

    Google Scholar 

  158. F. Harary and I.C. Ross, A procedure for clique detection using the group matrix, Sociometry, Vol. 20: 205–215, 1957.

    MathSciNet  Google Scholar 

  159. J. Hasselberg, P.M. Pardalos and G. Vairaktarakis, Test case generators and computational results for the maximum clique problem, J. Global Optim., Vol. 3: 463–482, 1993.

    Google Scholar 

  160. J. Hastad, Testing of the long code and hardness clique, Proc. 28th Ann. Symp. Theory of Comput.: 11-19, 1996.

    Google Scholar 

  161. J. Hastad, Clique is hard to approximate within n 1— ß, Proc. 37th Ann. Symp. Found. Comput. Sci.: 627–636, 1996.

    Google Scholar 

  162. S. Haykin, Neural Networks: A Comprehensive Foundation, Macmillan, New York, 1994.

    MATH  Google Scholar 

  163. R.B. Hayward, Weakly triangulated graphs, J. of Combin. Theory B, Vol. 39: 200–209, 1985.

    Article  MathSciNet  MATH  Google Scholar 

  164. R. Hayward, C.T. Hoang and F. Maffray, Optimizing weakly triangulated graphs, Graphs and Combinatorics, Vol. 5: 339–349, 1989. See also Erratum, Vol. 6: 33–35, 1990.

    Google Scholar 

  165. I. Heller, On linear systems with integral valued solutions, Pacific J. Math., Vol. 7: 1351–1364, 1957

    Google Scholar 

  166. C. Helmberg, F. Rendl, R.J. Vanderbei and H. Wolkowicz, An interior-point method for semidefinite programming, SIAM J. Optim., Vol. 6: 342–361, 1996.

    MathSciNet  MATH  Google Scholar 

  167. J. Hertz, A. Krogh and R.G. Palmer, Introduction to the Theory of Neural Computation, Addison-Wesley, Redwood City, CA, 1991.

    Google Scholar 

  168. A. Hertz, E. Taillard and D. de Werra, Tabu search, in [2]: 121–136.

    Google Scholar 

  169. M. Hifi, A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems, J. Oper. Res. Soc. Vol. 48: 612–622, 1997.

    MATH  Google Scholar 

  170. C.W. Ho and R.C.T. Lee, Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring of chordal graphs, Inform. Proc. Lett., Vol. 28: 301–309, 1988.

    MathSciNet  MATH  Google Scholar 

  171. J. Hofbauer and K. Sigmund, Evolutionary Games and Population Dynamics, Cambridge University Press, Cambridge, UK, 1998.

    Book  MATH  Google Scholar 

  172. J.H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, MI, 1975.

    Google Scholar 

  173. S. Homer and M. Peinado, Experiments with polynomial-time CLIQUE approximation algorithms on very large graphs, in [189]: 147–167, 1996.

    Google Scholar 

  174. J.J. Hopfield and D.W. Tank, “Neural” computation of decisions in optimization problems, Biol. Cybern., Vol. 52: 141–152, 1985.

    MathSciNet  MATH  Google Scholar 

  175. R. Horaud and T. Skordas, Stereo correspondence through feature grouping and maximal cliques, IEEE Trans. Pattern Anal. Machine Intell., Vol. 11: 1168–1180, 1989.

    Article  Google Scholar 

  176. R.A. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, UK, 1985.

    Google Scholar 

  177. D.J. Houck, On the vertex packing problem, Ph.D. dissertation, The Johns Hopkins University, Baltimore, 1974.

    Google Scholar 

  178. D.J. Houck and R.R. Vemuganti, An algorithm for the vertex packing problem Oper. Res. Vol. 25: 773–787 1977.

    Google Scholar 

  179. W.L. Hsu, Maximum weight clique algorithms for circular-arc graphs and circle graphs, SIAM J. Comput., Vol. 14: 224–231, 1985.

    Article  MathSciNet  MATH  Google Scholar 

  180. W.L. Hsu, The coloring and maximum independent set problems on planar perfect graphs, J. ACM, Vol. 35: 535–563, 1988.

    Article  Google Scholar 

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

    Google Scholar 

  182. H.B. Hunt III, M.V. Marathe, V. Radhakrishnan and R.E. Stearns, The complexity of planar counting problems, SIAM J. Comput., Vol. 27: 1142–1167, 1998.

    Article  MathSciNet  MATH  Google Scholar 

  183. A. Jagota, Approximating Maximum Clique with a Hopfield Network, IEEE Trans. Neural Networks, Vol. 6: 724–735, 1995.

    Article  Google Scholar 

  184. A. Jagota (ed.), Neural Networks for Combinatorial Optimization J. Artif. Neural Networks Vol. 2 1995.

    Google Scholar 

  185. A. Jagota and K.W. Regan, Performance of neural net heuristics for maximum clique on diverse highly compressible graphs, J. Global Optim., Vol. 10: 439–465, 1997.

    Article  MathSciNet  MATH  Google Scholar 

  186. A. Jagota, L. Sanchis, and R. Ganesan, Approximately solving maximum clique using neural networks and related heuristics, in [189]: 169–204, 1996.

    Google Scholar 

  187. M. Jerrum, Large cliques elude the Metropolis process, Random Structures and Algorithms, Vol. 3: 347–359, 1992.

    Article  MathSciNet  MATH  Google Scholar 

  188. D.S. Johnson, Approximation algorithms for combinatorial problems, J. Comput. Syst. Sci., Vol. 9: 256–278, 1974.

    Article  MATH  Google Scholar 

  189. D.S. Johnson and M.A. Trick (eds.), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge,DI-MACS Vol. 26,American Mathematical Society, 1996 (see also http:/ /dimacs.rutgers.edu/Volumes/Vo126.html).

    Google Scholar 

  190. D.S. Johnson, M. Yannakakis and C.H. Papadimitriou, On generating all maximal independent sets, Inform. Proc. Lett., Vol. 27: 119–123, 1988.

    Article  MathSciNet  MATH  Google Scholar 

  191. L.F. Johnson, Determining cliques of a graph, Proc. 5th Manitoba Conf. on Numer. Math.: 429–437, 1975.

    Google Scholar 

  192. H.C. Johnston, Cliques of a graph: Variations on the Bron-Kerbosch algorithm, Int. J. Comput. Inform. Sci., Vol. 5: 209–238, 1976.

    Article  MathSciNet  MATH  Google Scholar 

  193. N. Karmarkar, K.G. Ramakrishnan and M.G.C. Resende, An interior point approach to the maximum independent set problem in dense random graphs, Proc. XV Latin American Conference on Informatics, Santiago, Chile, I: 241–260, 1989.

    Google Scholar 

  194. R.M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, R.E. Miller and J.W. Thatcher (eds.), Plenum Press, New York: 85–103, 1972.

    Google Scholar 

  195. R.M. Karp and A. Wigderson, A fast parallel algorithm for the maximal independent set problem, J. ACM, Vol. 32: 762–773, 1985.

    Article  MathSciNet  MATH  Google Scholar 

  196. M. Karpinski and A. Zelikovsky, Approximating dense cases of covering problems, in P.M. Pardalos et al. (eds), Network Design: Connectivity and Facilities Location, DIMACS Workshop, April 28–30, 1997. AMS-DIMACS Ser. Discr. Math. Theor. Comput. Sci. Vol. 40: 169–178, 1998.

    Google Scholar 

  197. T. Kashiwabara, S. Masuda, K, Nakajima and T. Fujisawa, Generation of maximum independent sets of a bipartite graph and maximum cliques of a circular-arc-graph, J. Algorithms, Vol. 13: 161–174, 1992.

    Article  MathSciNet  MATH  Google Scholar 

  198. O.H. Keller, Über die lückenlose Erfüllung des Raumes mit Würfeln (in German), J. Reine Angew. Math., Vol. 163: 231–248, 1930.

    MATH  Google Scholar 

  199. P. Kikusts, Another algorithm determining the independence number of a graph, Elektron. Inf. Verarb. Kybern. ELK 22: 157–166, 1986.

    MathSciNet  MATH  Google Scholar 

  200. D.S. Kim and D.-Z. Du, On conflict-free channel set assignments for optical cluster-based hypercube networks, In DIMACS Series Vol. 46: 109–116, American Mathematical Society (1999).

    Google Scholar 

  201. S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi, Optimization by simulated annealing, Science, Vol. 220: 671–680, 1983.

    Article  MathSciNet  MATH  Google Scholar 

  202. P.N. Klein, Efficient parallel algorithms for chordal graphs, Proc. 29th Ann. Symp. Found. Computer Sci.: 150–161, 1988.

    Google Scholar 

  203. J. Kleinberg and M.X. Goemans, The Lovâsz theta function and a semidefinite programming relaxation of vertex cover, SIAM J. Discr. Math. Vol. 11: 196–204, 1997.

    Article  MathSciNet  Google Scholar 

  204. D.E. Knuth, The sandwich theorem, Electr. J. Combin.,Vol. 1: Al, 1994 (http://www2.combinatorics.org/Volume_1/volumel.html#A1).

    Google Scholar 

  205. R. Kopf and G. Ruhe, A computational study of the weighted independent set problem for general graphs, Found. Control Engin., Vol. 12: 167–180, 1987.

    MathSciNet  MATH  Google Scholar 

  206. D. Kozen, A clique problem equivalent to graph isomorphism, SIGACT News: 50–52, Summer 1978.

    Google Scholar 

  207. J.C. Lagarias and P.W. Shor, Keller’s cube-tiling conjecture is false in high dimensions, Bull. Amer. Math. Soc. New Ser., Vol. 27: 279–283, 1992.

    Article  MathSciNet  MATH  Google Scholar 

  208. P.J.M. van Laarhoven and E.H.L. Aarts, Simulated Annealing: Theory and Applications, Reidel, Dordrecht, 1987.

    Book  MATH  Google Scholar 

  209. E.L. Lawler, Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, 1976.

    Google Scholar 

  210. L.J. Leifman, On construction of all maximal complete subgraphs (cliques) of a graph, Technical Report, Dept. of Mathematics., University of Haifa, Israel, 1976.

    Google Scholar 

  211. F. Lin and K. Lee, A parallel computation network for the maximum clique problem, in Proc. 1st Int. Conf. Fuzzy Theory Tech., Baton Rouge, Louisiana, 1992.

    Google Scholar 

  212. R.J. Lipton, On proving that a graph has no large clique: A connection with Ramsey theory, Inform. Proc. Lett., Vol. 58: 39–42, 1996.

    Article  MathSciNet  MATH  Google Scholar 

  213. C.-K. Looi, Neural network methods in combinatorial optimization, Comput. Oper. Res.,Vol. 19: 191–208, 1992.

    Google Scholar 

  214. E. Loukakis, A new backtracking algorithm for generating the family of maximal independent sets of a graph, Comp. Math. Appl., Vol. 9: 583–589, 1983.

    Article  MathSciNet  MATH  Google Scholar 

  215. E. Loukakis and C. Tsouros, A depth first search algorithm to generate the family of maximal independent sets of a graph lexicographically, Computing, Vol. 27: 249–266, 1981.

    Article  MathSciNet  Google Scholar 

  216. E. Loukakis and C. Tsouros, Determining the number of internal stability of a graph, Int. J. Comp. Math, Vol. 11: 207–220, 1982.

    Article  MathSciNet  MATH  Google Scholar 

  217. E. Loukakis and C. Tsouros, An algorithm for the maximum internally stable set in a weighted graph, Int. J. Comput. Math., Vol. 13: 117129, 1983.

    Google Scholar 

  218. L. Lovâsz, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, Vol. 25: 1–7, 1979.

    Google Scholar 

  219. L. Lovâsz and A. Schrijver, Cones of matrices and set-functions and 0–1 optimization, SIAM J. Optim.,Vol. 1: 166–190, 1991.

    Google Scholar 

  220. M. Luby, A simple parallel algorithm for the maximum independent set problem, SIAM J. Comput., Vol. 15: 1036–1053, 1986.

    Article  MathSciNet  MATH  Google Scholar 

  221. J. MacWilliams and N.J.A. Sloane, The Theory of Error Correcting Codes, North-Holland, Amsterdam, 1979.

    MATH  Google Scholar 

  222. K. Maghout, Sur la determination des nombres de stabilite et du nombre chromatique d’un graphe, C.R. Acad. Sci., Paris, Vol. 248: 2522–2523, 1959.

    MathSciNet  Google Scholar 

  223. G.K. Manacher and T.A. Mankus, Finding a maximum clique in a set of proper circular arcs in 0(n) with applications, Int. J. Found. Comput. Sci., Vol. 8: 443–467, 1997.

    Article  MATH  Google Scholar 

  224. C. Mannino and A. Sassano, Edge projection and the maximum cardinality stable set problem, in [189]: 205–219, 1996.

    Google Scholar 

  225. E. Marchiori, A simple heuristic based genetic algorithm for the maximum clique problem, Proc. ACM Symp. Appl. Comput.: 366–373, 1998.

    Google Scholar 

  226. P.M. Marcus, Derivation of maximal compatibles using boolean algebra, IBM J. Res. Develop., Vol. 8: 537–538, 1964.

    Google Scholar 

  227. S. Masuda and K. Nakajima, An optimal algorithm for finding a maximum independent set of a circular-arc graph, SIAM J. Comput.,Vol. 17: 41–52, 1988

    Google Scholar 

  228. S. Masuda, K. Nakajima, T, Kashiwabara and T. Fujisawa, Efficient algorithms for finding maximum cliques of an overlap graph, Networks, Vol. 20: 157–171, 1990.

    Article  MathSciNet  MATH  Google Scholar 

  229. D.W. Matula, On the complete subgraphs of a random graph, Proc. 2nd Conf. Combin. Theory Appl., Chapel Hill, NC: 356–369, 1970.

    Google Scholar 

  230. D.W. Matula, The largest clique size in a random graph, Technical Report CS 7608, Department of Computer Science, Southern Methodist University, 1976.

    Google Scholar 

  231. W. Meeusen and L. Cuyvers, Clique detection in directed graphs: A new algorithm, J. Comput. Appl. Math., Vol. 1: 185–193, 1975.

    MathSciNet  MATH  Google Scholar 

  232. W. Meeusen and L. Cuyvers, An annotated bibliography of clique-detection algorithms and related graph-theoretical problems, CAM Discussion Paper 7909, State University Center Antwerp, 1979.

    Google Scholar 

  233. H. Meyniel, On the perfect graph conjecture, Discr. Math., Vol. 16: 339–342, 1976.

    Article  MathSciNet  Google Scholar 

  234. H. Meyniel, A new property of imperfect graphs and some consequences, Europ. J. Combin., Vol. 8: 313–316, 1987.

    MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  236. B. Mohar and S. Poljak, Eigenvalues in combinatorial optimization, In Combinatorial and Graph-Theoretic Problems in Linear Algebra R. Brualdi, S. Friedland and V. Klee, eds., IMA Volumes in Mathematics and Its Applications, Vol. 50, Springer, Berlin, 1993.

    Google Scholar 

  237. J.W. Moon and L. Moser, On cliques in graphs, Israel Journal of Mathematics, Vol. 3: 23–28, 1965.

    Article  MathSciNet  MATH  Google Scholar 

  238. T.S. Motzkin and E.G. Straus, Maxima for graphs and a new proof of a theorem of Turân, Canad. J. Math., Vol. 17: 533–540, 1965.

    Article  MathSciNet  MATH  Google Scholar 

  239. G.D. Mulligan and D.G. Corneil, Corrections to Bierstone’s algorithm for generating cliques, J. ACM, Vol. 19: 244–247, 1972.

    Article  MATH  Google Scholar 

  240. W.J. Murphy, Computing independent sets in graphs with large girth, Discr. Appl. Math., Vol. 36: 167–170, 1992.

    Article  Google Scholar 

  241. A.S. Murthy, G. Parthasarathy and V.U.K. Sastry, Clique finding A genetic approach, Proc. 1st IEEE Conf. Evolutionary Comput.: 18–21, 1994.

    Google Scholar 

  242. J. Naor, M. Naor and A.A. Schaffer, Fast parallel algorithms for chordal graphs, Proc. 19th Annual ACM Symp. Theory Comput.: 355364, 1987.

    Google Scholar 

  243. G.L. Nemhauser and G. Sigismondi, A strong cutting plane/branchand bound algorithm for node packing, J. Opl. Res. Soc., Vol. 43: 443–457, 1992.

    MATH  Google Scholar 

  244. G.L. Nemhauser and L.E. Trotter„ Properties of vertex packings and independence system polyhedra, Math. Programming, Vol. 6: 48–61, 1974.

    Article  MathSciNet  MATH  Google Scholar 

  245. G.L. Nemhauser and L.E. Trotter, Vertex packings: Structural properties and algorithms, Math. Programming, Vol. 8: 232–248, 1975.

    Article  MathSciNet  MATH  Google Scholar 

  246. G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization, J. Wiley 86 Sons, New York, 1988.

    Google Scholar 

  247. H. Ogawa, Labeled point pattern matching by Delaunay triangulation and maximal cliques, Pattern Recognition, Vol. 19: 35–40, 1986.

    Article  Google Scholar 

  248. S. Olariu, Weak bipolarizable graphs, Discr. Math., Vol. 74: 159–171, 1989.

    Article  MathSciNet  MATH  Google Scholar 

  249. R.E. Osteen, Clique detection algorithms based on line addition and line removal, SIAM J. Appl. Math., Vol. 26: 126–135, 1974.

    Article  MathSciNet  MATH  Google Scholar 

  250. R.E. Osteen and J.T. Tou, A clique-detection algorithm based on neighborhoods in graphs, Int. J. Comput. Inform. Sci., Vol. 2: 257268, 1973.

    Google Scholar 

  251. Q. Ouyang, P.D. Kaplan, S. Liu and A. Libchaber, DNA solutions of the maximal clique problem, Science, Vol. 278: 446–449, 1997.

    Article  Google Scholar 

  252. M.W. Padberg, Covering, packing and knapsack problems, Ann. Discr. Math., Vol. 4: 265–287, 1979.

    Article  MathSciNet  MATH  Google Scholar 

  253. A. Panconesi and D. Ranjan, Quantifiers and approximation, Proc. 22nd ACM Ann. Symp. Theory of Comput.: 446–456, 1990.

    Google Scholar 

  254. A. Panconesi and D. Ranjan, Quantifiers and approximation, Theor. Comput. Sci., Vol. 107: 145–163, 1993.

    Article  MathSciNet  MATH  Google Scholar 

  255. C. Papadimitriou, Computational Complexity, Addison-Wesley, Amsterdam, 1994.

    MATH  Google Scholar 

  256. C. Papadimitriou and M. Yannakakis, The clique problem for planar graphs, Inform. Proc. Lett., Vol. 13: 131–133, 1981.

    Article  MathSciNet  Google Scholar 

  257. C. Papadimitriou and M. Yannakakis, Optimization, approximation and complexity classes, Proc. 20th Ann. ACM STOC: 229–234, 1988.

    Google Scholar 

  258. C. Papadimitriou and M. Yannakakis, Optimization, approximation and complexity classes, J. Comput. Syst. Sci., Vol. 43: 425–440, 1991.

    Article  MathSciNet  MATH  Google Scholar 

  259. P.M. Pardalos, Continuous approaches to discrete optimization problems, in Nonlinear Optimization and Applications, G. Di Pillo and F. Giannessi, eds., Plenum Press, New York: 313–328, 1996.

    Google Scholar 

  260. P.M. Pardalos and N. Desai, An algorithm for finding a maximum weighted independent set in an arbitrary graph, Int. J. Comput. Math., Vol. 38: 163–175, 1991.

    Google Scholar 

  261. P.M. Pardalos and A.T. Phillips, A global optimization approach for solving the maximum clique problem, Int. J. Comput. Math., Vol. 33: 209–216, 1990.

    MATH  Google Scholar 

  262. P.M. Pardalos, J. Rappe and M.G.C. Resende, An Exact Parallel Algorithm for the Maximum Clique Problem, in High Performance Algorithms and Software in Nonlinear Optimization, R. De Leone, A. Murlí, P.M. Pardalos and G. Toraldo (eds.), Kluwer: 279–300, Dordrecht, 1998.

    Google Scholar 

  263. P. M. Pardalos and G. Rodgers, Parallel branch and bound algorithms for quadratic zero-one programming on a hypercube architecture, Ann. Oper. Res., Vol. 22: 271–292, 1990.

    Article  MathSciNet  MATH  Google Scholar 

  264. P. M. Pardalos and G. Rodgers, Computational aspects of a branch and bound algorithm for quadratic zero-one programming, Computing, Vol. 45: 131–144, 1990.

    Article  MathSciNet  MATH  Google Scholar 

  265. P.M. Pardalos and G.P. Rodgers, A branch and bound algorithm for the maximum clique problem, Comput. Oper. Res., Vol. 19: 363–375, 1992.

    MATH  Google Scholar 

  266. P.M. Pardalos and J. Xue, The maximum clique problem, J. Global Optim., Vol. 4: 301–328, 1994.

    MathSciNet  MATH  Google Scholar 

  267. K. Park and B. Carter, On the effectiveness of genetic search in combinatorial optimization, Technical Report BU-CS-94–010,Computer Science Dept., Boston University, 1994. (a shorter version appears in: Proc. 10th ACM Symp. Appl. Comput.,1995.)

    Google Scholar 

  268. M.C. Paull and S.H. Unger, Minimizing the number of states in incompletely specified sequential switching functions, IRE Trans. Electr. Comput., Vol. EC-8: 356–367, 1959.

    Google Scholar 

  269. E.R. Peay, Jr., An iterative clique detection procedure, Michigan Math. Psychol. Program: MMPP 70–4, 1970.

    Google Scholar 

  270. E.R. Peay, Jr., Hierarchical clique structures, Sociometry, Vol. 37: 54–65, 1974.

    Article  Google Scholar 

  271. M. Pelillo, Relaxation labeling networks for the maximum clique problem, J. Artif. Neural Networks, Vol. 2: 313–328, 1995.

    Google Scholar 

  272. M. Pelillo, A unifying framework for relational structure matching, in: Proc. 14th Int. Conf. Pattern Recognition: 1316–1319, 1998.

    Google Scholar 

  273. M. Pelillo, Replicator equations, maximal cliques, and graph isomorphism, Neural Computation, to appear, 1999.

    Google Scholar 

  274. M. Pelillo and A. Jagota, Feasible and infeasible maxima in a quadratic program for maximum clique, J. Artif. Neural Networks, Vol. 2: 41 1420, 1995.

    Google Scholar 

  275. M. Pelillo, K. Siddiqi and S.W. Zucker, Matching hierarchical structures using association graphs, in H. Burkhardt and B. Neumann (eds.), Computer Vision—ECCV’98 (Lecture Notes in Computer Science, Vol. 1407), Springer, Berlin: 3–16, 1998.

    Google Scholar 

  276. O. Perron, Über lückenlose Ausfüllung des n-dimensionalen Raumes durch kongruente Würfel (in German), Math. Z., Vol. 46: 1–26, 161180. Zbl 22, 202, 1940.

    Google Scholar 

  277. C. Peterson and B. Söderberg, Artificial neural networks, in [2]: 173213, 1997.

    Google Scholar 

  278. J.C. Picard and M. Queyranne, On the integer-valued variables in the linear vertex packing problem, Math. Programming, Vol. 12: 97–101, 1977.

    Article  MathSciNet  MATH  Google Scholar 

  279. F. Pla and J.A. Marchant, Matching feature points in image sequences through a region-based method, Comput. Vision Image Understanding, Vol. 66: 271–285, 1997.

    Article  Google Scholar 

  280. F.P. Preparata, G. Metze and R.T. Chien, On the connection assignment problem of diagnosable systems, IEEE Trans. Electr. Comput., Vol. 16: 848–854, 1967.

    Article  MATH  Google Scholar 

  281. W.R. Pulleyblank, Minimum node covers and 2-bicritical graphs, Math. Programming, Vol. 17: 91–103, 1979.

    Article  MathSciNet  MATH  Google Scholar 

  282. B. Radig, Image sequence analysis using relational structures, Pattern Recognition, Vol. 17: 161–167, 1984.

    Article  Google Scholar 

  283. P. Raghavan, Probabilistic construction of deterministic algorithms: Approximating packing integer programs, J. Comput. Syst. Sci., Vol. 37: 130–143, 1988.

    Article  MathSciNet  MATH  Google Scholar 

  284. J. Ramanujam and P. Sadayappan, Optimization by neural networks, Proc. IEEE Int. Conf. Neural Networks: 325–332, 1988.

    Google Scholar 

  285. M.C.G. Resende, T.A. Feo, and S.H. Smith, Fortran subroutines for approximate solution of maximum independent set problems using GRASP, ACM Transactions on Mathematical Software, to appear 1999.

    Google Scholar 

  286. J.M. Robson, Algorithms for maximum independent sets, J. Algorithms, Vol. 7: 425–440, 1986.

    Article  MathSciNet  MATH  Google Scholar 

  287. D.J. Rose, Triangulated graphs and the elimination process, J. Math. Anal. Appl., Vol. 32: 597–609, 1970.

    Article  MathSciNet  MATH  Google Scholar 

  288. D.J. Rose, R.E. Tarjan and G.S. Leuker, Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., Vol. 5: 266–283, 1976.

    Article  MathSciNet  MATH  Google Scholar 

  289. D. Rotem and J. Urrutia, Finding maximum cliques in circle graphs, Networks, Vol. 11: 269–278, 1981.

    Article  MathSciNet  MATH  Google Scholar 

  290. B.E. Sagan, A note on independent sets in trees, SIAM J. Discr. Math., Vol. 1: 105–108, 1988.

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

  292. C.E. Shannon, Certain results in coding theory for noisy channels, Inform. and Control, Vol. 1: 6–25, 1957.

    Article  MathSciNet  MATH  Google Scholar 

  293. N. Z. Shor, Dual quadratic estimates in polynomial and Boolean programming, in Computational Methods in Global Optimization, P. M. Pardalos and J. B. Rosen (eds.), Ann. Oper. Res., Vol. 25: 163–168, 1990.

    Google Scholar 

  294. Y. Shrivastava, S. Dasgupta, and S.M. Reddy, Neural network solutions to a graph theoretic problem, in Proc. IEEE Int. Symp. Circuits Syst.: 2528–2531, 1990.

    Chapter  Google Scholar 

  295. Y. Shrivastava, S. Dasgupta, and S.M. Reddy, Guaranteed convergence in a class of Hopfield networks, IEEE Trans. Neural Networks, Vol. 3: 951–961, 1992.

    Article  Google Scholar 

  296. N.J.A. Sloane, Unsolved problems in graph theory arising from the study of codes, J. Graph Theory Notes of New York, Vol. 18: 11–20, 1989.

    Google Scholar 

  297. P. Soriano and M. Gendreau, Tabu search algorithms for the maximum clique problem, in [189]: 221–242, 1996.

    Google Scholar 

  298. P. Soriano and M. Gendreau, Diversification strategies in tabu search algorithms for the maximum clique problem, Ann. Oper. Res., Vol. 63: 189–207, 1996.

    MATH  Google Scholar 

  299. V.T. Sós and E.G. Straus, Extremal of functions on graphs with applications to graphs and hypergraphs, J. Combin. Theory B, Vol. 32: 246–257, 1982

    Google Scholar 

  300. S.K. Stein, Algebraic tiling, Amer. Math. Monthly, Vol. 81: 445–462, 1974.

    MATH  Google Scholar 

  301. S. Szabó, A reduction of Keller’s conjecture, Periodica Math. Hung., Vol. 17: 265–277, 1986.

    Article  MATH  Google Scholar 

  302. Y. Takefuji, Neural Network Parallel Computing, Kluwer, Dordrecht, 1992.

    Book  MATH  Google Scholar 

  303. Y. Takefuji, L. Chen, K. Lee and J. Huffman, Parallel algorithms for finding a near-maximum independent set of a circle graph, IEEE Trans. Neural Networks, Vol. 1: 263–267, 1990.

    Google Scholar 

  304. R.E. Tarjan, Finding a maximum clique, Technical Report 72–123, Computer Sci. Dept., Cornell University, Ithaca, NY, 1972.

    Google Scholar 

  305. R.E. Tarjan and A.E. Trojanowski, Finding a maximum independent set, SIAM J. Comput., Vol. 6: 537–546, 1977.

    MathSciNet  MATH  Google Scholar 

  306. R.E. Tarjan and M Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., Vol. 13: 566–579, 1984.

    MathSciNet  MATH  Google Scholar 

  307. E. Tomita, Y. Kohata and H. Takahashi, A simple algorithm for finding a maximum clique, Technical Report UEC-TR-05, 1988.

    Google Scholar 

  308. E. Tomita, S. Mitsuma and H. Takahashi, Two algorithms for finding a near-maximum clique, Technical Report UEC-TR-C1, 1988.

    Google Scholar 

  309. E. Tomita, A. Tanaka and H. Takahashi, The worst-case time complexity for finding all the cliques, Technical Report UEC-TR-05, 1988.

    Google Scholar 

  310. S. Tsukiyama, M. Ide, H. Aviyoshi and I. Shirakawa, A new algorithm for generating all the maximum independent sets, SIAM J. Comput., Vol. 6: 505–517, 1977.

    Article  MathSciNet  MATH  Google Scholar 

  311. P. Turin, On an extremal problem in graph theory (in Hungarian), Mat. és Fiz. Lapok, Vol. 48: 436–452, 1941.

    Google Scholar 

  312. L.G. Valiant, The complexity of enumeration and reliability problems, SIAM J. Comput., Vol. 8: 410–421, 1979.

    Article  MathSciNet  MATH  Google Scholar 

  313. O. Verbitsky, On the hardness of approximating some optimization problems that are supposedly easier that MAX CLIQUE, Comb. Probab. Comput. Vol. 4: 167–180, 1995.

    Article  MathSciNet  MATH  Google Scholar 

  314. M. Vingron and P. Argos, Motif recognition and alignment for many sequences by comparison of dot-matrices, J. Molecular Biol., Vol. 218: 33–43, 1991.

    Article  Google Scholar 

  315. M. Vingron and P.A. Pevzner, Multiple sequence comparison and consistency on multipartite graphs. Adv. Appl. Math Vol. 16: 1–22, 1995.

    Article  MathSciNet  MATH  Google Scholar 

  316. H.S. Wilf, The eigenvalues of a graph and its chromatic number, J. London Math. Soc., Vol. 42: 330–332, 1967.

    Article  MathSciNet  MATH  Google Scholar 

  317. H.S. Wilf, Algorithms and Complexity, Prentice-Hall, Englewood Cliffs, NJ, 1986.

    MATH  Google Scholar 

  318. H.S. Wilf, Spectral bounds for the clique and independence numbers of graphs, J. Combin. Theory B, Vol. 40: 113–117, 1986.

    Article  MathSciNet  MATH  Google Scholar 

  319. S. Wimer, R.Y. Pinter and J. Feldman, Optimal chaining of CMOS transistors in a functional cell, IEEE Trans. Computer-Aided Design, Vol. 6: 795–801, 1987.

    Article  Google Scholar 

  320. J. Wu, T. Harada and T. Fukao, New method to the solution of maximum clique problem: Mean-field approximation algorithm and its experimentation. Proc. IEEE Int. Conf. Syst., Man, Cybern.: 22482253, 1994.

    Google Scholar 

  321. J. Xue, Fast Algorithms for Vertex Packing and Related Problems, Ph.D Thesis, GSIA, Carnegie Mellon University, 1991.

    Google Scholar 

  322. J. Xue, Edge-maximal triangulated subgraphs and heuristics for the maximum clique problem, Networks, Vol. 24: 109–120, 1994.

    MATH  Google Scholar 

  323. M. Yannakakis, On the approximation of maximum satisfiability, Proc. 3rd Annual ACM-SIAM Symp. Discr. Algorithms, 1992.

    Google Scholar 

  324. M.-S. Yu, L. Yu and S.-J. Chang, Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs, Inform. Proc. Lett., Vol. 46: 7–11, 1993.

    Google Scholar 

  325. B.-T. Zhang and S.-Y. Shin, Code optimization for DNA computing of maximal cliques, in Advances in Soft Computing—Engineering and Design, Springer, Berlin, 1998.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Statistik, Operations Research und Computerverfahren, Universität Wien, Universitätsstraβe 5, A-1010, Wien, Austria

    Immanuel M. Bomze

  2. Dipartimento di Fisica, Università di Trieste, Via Valerio 2, I-34127, Trieste, Italy

    Marco Budinich

  3. Center for Applied Optimization, ISE Department University of Florida, Gainesville, FL, 32611, USA

    Panos M. Pardalos

  4. Dipartimento di Informatica, Università Ca’ Foscari di Venezia, Via Torino 155, 30172, Venezia Mestre, Italy

    Marcello Pelillo

Authors
  1. Immanuel M. Bomze
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marco Budinich
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Panos M. Pardalos
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Marcello Pelillo
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, University of Minnesota, USA

    Ding-Zhu Du

  2. Institute of Applied Mathematics, Academia Sinica, P. R. China

    Ding-Zhu Du

  3. Department of Industrial and Systems Engineering, University of Florida, USA

    Panos M. Pardalos

Rights and permissions

Reprints and permissions

Copyright information

© 1999 Springer Science+Business Media Dordrecht

About this chapter

Cite this chapter

Bomze, I.M., Budinich, M., Pardalos, P.M., Pelillo, M. (1999). The Maximum Clique Problem. In: Du, DZ., Pardalos, P.M. (eds) Handbook of Combinatorial Optimization. Springer, Boston, MA. https://doi.org/10.1007/978-1-4757-3023-4_1

Download citation

  • DOI: https://doi.org/10.1007/978-1-4757-3023-4_1

  • Publisher Name: Springer, Boston, MA

  • Print ISBN: 978-1-4419-4813-7

  • Online ISBN: 978-1-4757-3023-4

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation