Clique problem (English Wikipedia)

Analysis of information sources in references of the Wikipedia article "Clique problem" in English language version.

Last modified: 02:02:18, 10 August 2026 (UTC)

Ref.Un. Ref.Website

Global rank English rank

6558doi.org

2^nd place

1110ams.org

434^th place

249^th place

76arxiv.org

49^th place

31^st place

65web.archive.org

1^st place

55adsabs.harvard.edu

14^th place

9^th place

55nih.gov

5^th place

44books.google.com

3^rd place

33jstor.org

23^rd place

15^th place

22unt.edu

1,621^st place

852^nd place

22rutgers.edu

2,011^th place

1,139^th place

224mhz.de

low place

22weizmann.ac.il

6,932^nd place

9,400^th place

21berkeley.edu

621^st place

429^th place

11dtic.mil

934^th place

530^th place

11inria.fr

6,372^nd place

5,582^nd place

11labri.fr

low place

11archive.org

6^th place

11insilab.org

low place

11mgvis.com

low place

11zenodo.org

737^th place

426^th place

11vldb.org

low place

11hdl.handle.net

66^th place

34^th place

11kth.se

low place

11u-szeged.hu

9,326^th place

low place

4mhz.de (Global: low place; English: low place)

Cook (1971). Cook, S. A. (1971), "The complexity of theorem-proving procedures", Proc. 3rd ACM Symposium on Theory of Computing, pp. 151–158, doi:10.1145/800157.805047.
Cook (1971) gives essentially the same reduction, from 3-SAT instead of Satisfiability, to show that subgraph isomorphism is NP-complete. Cook, S. A. (1971), "The complexity of theorem-proving procedures", Proc. 3rd ACM Symposium on Theory of Computing, pp. 151–158, doi:10.1145/800157.805047.

adsabs.harvard.edu (Global: 14^th place; English: 9^th place)

ui.adsabs.harvard.edu

National Research Council Committee on Mathematical Challenges from Computational Chemistry (1995). See in particular pp. 35–36. National Research Council Committee on Mathematical Challenges from Computational Chemistry (1995), Mathematical Challenges from Theoretical/Computational Chemistry, National Academies Press, Bibcode:1995nap..book.4886N, doi:10.17226/4886, ISBN 978-0-309-05097-5.
Spirin & Mirny (2003). Spirin, Victor; Mirny, Leonid A. (2003), "Protein complexes and functional modules in molecular networks", Proceedings of the National Academy of Sciences, 100 (21): 12123–12128, Bibcode:2003PNAS..10012123S, doi:10.1073/pnas.2032324100, PMC 218723, PMID 14517352.
Ouyang et al. (1997). Although the title refers to maximal cliques, the problem this paper solves is actually the maximum clique problem. Ouyang, Q.; Kaplan, P. D.; Liu, S.; Libchaber, A. (1997), "DNA solution of the maximal clique problem", Science, 278 (5337): 446–449, Bibcode:1997Sci...278..446O, doi:10.1126/science.278.5337.446, PMID 9334300.
Childs et al. (2002). Childs, A. M.; Farhi, E.; Goldstone, J.; Gutmann, S. (2002), "Finding cliques by quantum adiabatic evolution", Quantum Information and Computation, 2 (3): 181–191, arXiv:quant-ph/0012104, Bibcode:2000quant.ph.12104C, doi:10.26421/QIC2.3.
Childs & Eisenberg (2005); Magniez, Santha & Szegedy (2007). Childs, A. M.; Eisenberg, J. M. (2005), "Quantum algorithms for subset finding", Quantum Information and Computation, 5 (7): 593–604, arXiv:quant-ph/0311038, Bibcode:2003quant.ph.11038C, doi:10.26421/QIC5.7. Magniez, Frédéric; Santha, Miklos; Szegedy, Mario (2007), "Quantum algorithms for the triangle problem", SIAM Journal on Computing, 37 (2): 413–424, arXiv:quant-ph/0310134, doi:10.1137/050643684.

ams.org (Global: 434^th place; English: 249^th place)

mathscinet.ams.org

Frank & Strauss (1986). Frank, Ove; Strauss, David (1986), "Markov graphs", Journal of the American Statistical Association, 81 (395): 832–842, doi:10.2307/2289017, JSTOR 2289017, MR 0860518.
The Keller graph used by Lagarias & Shor (1992) has 1048576 vertices and clique size 1024. They described a synthetic construction for the clique, but also used clique-finding algorithms on smaller graphs to help guide their search. Mackey (2002) simplified the proof by finding a clique of size 256 in a 65536-vertex Keller graph. Lagarias, Jeffrey C.; Shor, Peter W. (1992), "Keller's cube-tiling conjecture is false in high dimensions", Bulletin of the American Mathematical Society, New Series, 27 (2): 279–283, arXiv:math/9210222, doi:10.1090/S0273-0979-1992-00318-X, MR 1155280. Mackey, John (2002), "A cube tiling of dimension eight with no facesharing", Discrete and Computational Geometry, 28 (2): 275–279, doi:10.1007/s00454-002-2801-9, MR 1920144.
Sethuraman & Butenko (2015). Sethuraman, Samyukta; Butenko, Sergiy (2015), "The maximum ratio clique problem", Computational Management Science, 12 (1): 197–218, doi:10.1007/s10287-013-0197-z, MR 3296231.
Papadimitriou & Yannakakis (1981); Chiba & Nishizeki (1985). Papadimitriou, Christos H.; Yannakakis, Mihalis (1981), "The clique problem for planar graphs", Information Processing Letters, 13 (4–5): 131–133, doi:10.1016/0020-0190(81)90041-7, MR 0651460. Chiba, N.; Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing, 14 (1): 210–223, doi:10.1137/0214017.
Garey, Johnson & Stockmeyer (1976). Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1976), "Some simplified NP-complete graph problems", Theoretical Computer Science, 1 (3): 237–267, doi:10.1016/0304-3975(76)90059-1, MR 0411240.
See, e.g., Frank & Strauss (1986). Frank, Ove; Strauss, David (1986), "Markov graphs", Journal of the American Statistical Association, 81 (395): 832–842, doi:10.2307/2289017, JSTOR 2289017, MR 0860518.
Plummer (1993). Plummer, Michael D. (1993), "Well-covered graphs: a survey", Quaestiones Mathematicae, 16 (3): 253–287, doi:10.1080/16073606.1993.9631737, MR 1254158, archived from the original on May 27, 2012.
Cook (1985). Cook, Stephen A. (1985), "A taxonomy of problems with fast parallel algorithms", Information and Control, 64 (1–3): 2–22, doi:10.1016/S0019-9958(85)80041-3, MR 0837088.
Blair & Peyton (1993), Lemma 4.5, p. 19. Blair, Jean R. S.; Peyton, Barry (1993), "An introduction to chordal graphs and clique trees", Graph theory and sparse matrix computation, IMA Vol. Math. Appl., vol. 56, Springer, New York, pp. 1–29, doi:10.1007/978-1-4613-8369-7_1, ISBN 978-1-4613-8371-0, MR 1320296.
Amano & Maruoka (2005). Amano, Kazuyuki; Maruoka, Akira (2005), "A superpolynomial lower bound for a circuit computing the clique function with at most $(1/6)\log \log N$ negation gates", SIAM Journal on Computing, 35 (1): 201–216, doi:10.1137/S0097539701396959, MR 2178806.

archive.org (Global: 6^th place; English: 6^th place)

Balas & Yu (1986); Carraghan & Pardalos (1990); Pardalos & Rogers (1992); Östergård (2002); Fahle (2002); Tomita & Seki (2003); Tomita & Kameda (2007); Konc & Janežič (2007). Balas, E.; Yu, C. S. (1986), "Finding a maximum clique in an arbitrary graph", SIAM Journal on Computing, 15 (4): 1054–1068, doi:10.1137/0215075. Carraghan, R.; Pardalos, P. M. (1990), "An exact algorithm for the maximum clique problem", Operations Research Letters, 9 (6): 375–382, doi:10.1016/0167-6377(90)90057-C. Pardalos, P. M.; Rogers, G. P. (1992), "A branch and bound algorithm for the maximum clique problem", Computers & Operations Research, 19 (5): 363–375, doi:10.1016/0305-0548(92)90067-F. Östergård, P. R. J. (2002), "A fast algorithm for the maximum clique problem", Discrete Applied Mathematics, 120 (1–3): 197–207, doi:10.1016/S0166-218X(01)00290-6. Fahle, T. (2002), "Simple and fast: Improving a branch-and-bound algorithm for maximum clique", Proc. 10th European Symposium on Algorithms, Lecture Notes in Computer Science, vol. 2461, Springer-Verlag, pp. 47–86, doi:10.1007/3-540-45749-6_44, ISBN 978-3-540-44180-9. Tomita, E.; Seki, T. (2003), "An efficient branch-and-bound algorithm for finding a maximum clique", Discrete Mathematics and Theoretical Computer Science, Lecture Notes in Computer Science, vol. 2731, Springer-Verlag, pp. 278–289, doi:10.1007/3-540-45066-1_22, ISBN 978-3-540-40505-4. Tomita, E.; Kameda, T. (2007), "An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments", Journal of Global Optimization, 37 (1): 95–111, doi:10.1007/s10898-006-9039-7. Konc, J.; Janežič, D. (2007), "An improved branch and bound algorithm for the maximum clique problem" (PDF), MATCH Communications in Mathematical and in Computer Chemistry, 58 (3): 569–590. Source code

arxiv.org (Global: 49^th place; English: 31^st place)

The Keller graph used by Lagarias & Shor (1992) has 1048576 vertices and clique size 1024. They described a synthetic construction for the clique, but also used clique-finding algorithms on smaller graphs to help guide their search. Mackey (2002) simplified the proof by finding a clique of size 256 in a 65536-vertex Keller graph. Lagarias, Jeffrey C.; Shor, Peter W. (1992), "Keller's cube-tiling conjecture is false in high dimensions", Bulletin of the American Mathematical Society, New Series, 27 (2): 279–283, arXiv:math/9210222, doi:10.1090/S0273-0979-1992-00318-X, MR 1155280. Mackey, John (2002), "A cube tiling of dimension eight with no facesharing", Discrete and Computational Geometry, 28 (2): 275–279, doi:10.1007/s00454-002-2801-9, MR 1920144.
Cazals & Karande (2008); Eppstein, Löffler & Strash (2013). Cazals, F.; Karande, C. (2008), "A note on the problem of reporting maximal cliques", Theoretical Computer Science, 407 (1): 564–568, doi:10.1016/j.tcs.2008.05.010. Eppstein, David; Löffler, Maarten; Strash, Darren (2013), "Listing all maximal cliques in large sparse real-world graphs in near-optimal time", Journal of Experimental Algorithmics, 18 (3): 3.1, arXiv:1103.0318, doi:10.1145/2543629.
Eppstein, Löffler & Strash (2013). Eppstein, David; Löffler, Maarten; Strash, Darren (2013), "Listing all maximal cliques in large sparse real-world graphs in near-optimal time", Journal of Experimental Algorithmics, 18 (3): 3.1, arXiv:1103.0318, doi:10.1145/2543629.
Childs et al. (2002). Childs, A. M.; Farhi, E.; Goldstone, J.; Gutmann, S. (2002), "Finding cliques by quantum adiabatic evolution", Quantum Information and Computation, 2 (3): 181–191, arXiv:quant-ph/0012104, Bibcode:2000quant.ph.12104C, doi:10.26421/QIC2.3.
Meka, Potechin & Wigderson (2015). Meka, Raghu; Potechin, Aaron; Wigderson, Avi (2015), "Sum-of-squares lower bounds for planted clique", Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC '15), New York, NY, USA: ACM, pp. 87–96, arXiv:1503.06447, doi:10.1145/2746539.2746600, ISBN 978-1-4503-3536-2.
Childs & Eisenberg (2005); Magniez, Santha & Szegedy (2007). Childs, A. M.; Eisenberg, J. M. (2005), "Quantum algorithms for subset finding", Quantum Information and Computation, 5 (7): 593–604, arXiv:quant-ph/0311038, Bibcode:2003quant.ph.11038C, doi:10.26421/QIC5.7. Magniez, Frédéric; Santha, Miklos; Szegedy, Mario (2007), "Quantum algorithms for the triangle problem", SIAM Journal on Computing, 37 (2): 413–424, arXiv:quant-ph/0310134, doi:10.1137/050643684.

berkeley.edu (Global: 621^st place; English: 429^th place)

cs.berkeley.edu

Karp (1972). Karp, Richard M. (1972), "Reducibility among combinatorial problems", in Miller, R. E.; Thatcher, J. W. (eds.), Complexity of Computer Computations (PDF), New York: Plenum, pp. 85–103, archived from the original (PDF) on 2011-06-29, retrieved 2009-12-17.

books.google.com (Global: 3^rd place; English: 3^rd place)

Wasserman & Faust (1994). Wasserman, Stanley; Faust, Katherine (1994), Social Network Analysis: Methods and Applications, Structural Analysis in the Social Sciences, vol. 8, Cambridge University Press, p. 276, ISBN 978-0-521-38707-1.
National Research Council Committee on Mathematical Challenges from Computational Chemistry (1995). See in particular pp. 35–36. National Research Council Committee on Mathematical Challenges from Computational Chemistry (1995), Mathematical Challenges from Theoretical/Computational Chemistry, National Academies Press, Bibcode:1995nap..book.4886N, doi:10.17226/4886, ISBN 978-0-309-05097-5.
Muegge & Rarey (2001). See in particular pp. 6–7. Muegge, Ingo; Rarey, Matthias (2001), "Small molecule docking and scoring", Reviews in Computational Chemistry, vol. 17, pp. 1–60, doi:10.1002/0471224413.ch1, ISBN 9780471398455.
Skiena (2009), p. 526. Skiena, Steven S. (2009), The Algorithm Design Manual (2nd ed.), Springer, ISBN 978-1-84800-070-4.

doi.org (Global: 2^nd place; English: 2^nd place)

Rhodes et al. (2003). Rhodes, Nicholas; Willett, Peter; Calvet, Alain; Dunbar, James B.; Humblet, Christine (2003), "CLIP: similarity searching of 3D databases using clique detection", Journal of Chemical Information and Computer Sciences, 43 (2): 443–448, doi:10.1021/ci025605o, PMID 12653507.
Kuhl, Crippen & Friesen (1983). Kuhl, F. S.; Crippen, G. M.; Friesen, D. K. (1983), "A combinatorial algorithm for calculating ligand binding", Journal of Computational Chemistry, 5 (1): 24–34, doi:10.1002/jcc.540050105.
National Research Council Committee on Mathematical Challenges from Computational Chemistry (1995). See in particular pp. 35–36. National Research Council Committee on Mathematical Challenges from Computational Chemistry (1995), Mathematical Challenges from Theoretical/Computational Chemistry, National Academies Press, Bibcode:1995nap..book.4886N, doi:10.17226/4886, ISBN 978-0-309-05097-5.
Muegge & Rarey (2001). See in particular pp. 6–7. Muegge, Ingo; Rarey, Matthias (2001), "Small molecule docking and scoring", Reviews in Computational Chemistry, vol. 17, pp. 1–60, doi:10.1002/0471224413.ch1, ISBN 9780471398455.
Barrow & Burstall (1976). Barrow, H.; Burstall, R. (1976), "Subgraph isomorphism, matching relational structures and maximal cliques", Information Processing Letters, 4 (4): 83–84, doi:10.1016/0020-0190(76)90049-1.
Hamzaoglu & Patel (1998). Hamzaoglu, I.; Patel, J. H. (1998), "Test set compaction algorithms for combinational circuits", Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design, pp. 283–289, doi:10.1145/288548.288615, ISBN 1-58113-008-2.
Day & Sankoff (1986). Day, William H. E.; Sankoff, David (1986), "Computational complexity of inferring phylogenies by compatibility", Systematic Zoology, 35 (2): 224–229, doi:10.2307/2413432, JSTOR 2413432.
Samudrala & Moult (1998). Samudrala, Ram; Moult, John (1998), "A graph-theoretic algorithm for comparative modeling of protein structure", Journal of Molecular Biology, 279 (1): 287–302, doi:10.1006/jmbi.1998.1689, PMID 9636717.
Spirin & Mirny (2003). Spirin, Victor; Mirny, Leonid A. (2003), "Protein complexes and functional modules in molecular networks", Proceedings of the National Academy of Sciences, 100 (21): 12123–12128, Bibcode:2003PNAS..10012123S, doi:10.1073/pnas.2032324100, PMC 218723, PMID 14517352.
Frank & Strauss (1986). Frank, Ove; Strauss, David (1986), "Markov graphs", Journal of the American Statistical Association, 81 (395): 832–842, doi:10.2307/2289017, JSTOR 2289017, MR 0860518.
The Keller graph used by Lagarias & Shor (1992) has 1048576 vertices and clique size 1024. They described a synthetic construction for the clique, but also used clique-finding algorithms on smaller graphs to help guide their search. Mackey (2002) simplified the proof by finding a clique of size 256 in a 65536-vertex Keller graph. Lagarias, Jeffrey C.; Shor, Peter W. (1992), "Keller's cube-tiling conjecture is false in high dimensions", Bulletin of the American Mathematical Society, New Series, 27 (2): 279–283, arXiv:math/9210222, doi:10.1090/S0273-0979-1992-00318-X, MR 1155280. Mackey, John (2002), "A cube tiling of dimension eight with no facesharing", Discrete and Computational Geometry, 28 (2): 275–279, doi:10.1007/s00454-002-2801-9, MR 1920144.
Valiente (2002); Pelillo (2009). Valiente, Gabriel (2002), "Chapter 6: Clique, Independent Set, and Vertex Cover", Algorithms on Trees and Graphs, Springer, pp. 299–350, doi:10.1007/978-3-662-04921-1_6. Pelillo, Marcello (2009), "Heuristics for maximum clique and independent set", Encyclopedia of Optimization, Springer, pp. 1508–1520, doi:10.1007/978-0-387-74759-0_264, ISBN 978-0-387-74758-3.
Pelillo (2009). Pelillo, Marcello (2009), "Heuristics for maximum clique and independent set", Encyclopedia of Optimization, Springer, pp. 1508–1520, doi:10.1007/978-0-387-74759-0_264, ISBN 978-0-387-74758-3.
Sethuraman & Butenko (2015). Sethuraman, Samyukta; Butenko, Sergiy (2015), "The maximum ratio clique problem", Computational Management Science, 12 (1): 197–218, doi:10.1007/s10287-013-0197-z, MR 3296231.
Valiente (2002). Valiente, Gabriel (2002), "Chapter 6: Clique, Independent Set, and Vertex Cover", Algorithms on Trees and Graphs, Springer, pp. 299–350, doi:10.1007/978-3-662-04921-1_6.
Chiba & Nishizeki (1985). Chiba, N.; Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing, 14 (1): 210–223, doi:10.1137/0214017.
Papadimitriou & Yannakakis (1981); Chiba & Nishizeki (1985). Papadimitriou, Christos H.; Yannakakis, Mihalis (1981), "The clique problem for planar graphs", Information Processing Letters, 13 (4–5): 131–133, doi:10.1016/0020-0190(81)90041-7, MR 0651460. Chiba, N.; Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing, 14 (1): 210–223, doi:10.1137/0214017.
Garey, Johnson & Stockmeyer (1976). Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1976), "Some simplified NP-complete graph problems", Theoretical Computer Science, 1 (3): 237–267, doi:10.1016/0304-3975(76)90059-1, MR 0411240.
See, e.g., Frank & Strauss (1986). Frank, Ove; Strauss, David (1986), "Markov graphs", Journal of the American Statistical Association, 81 (395): 832–842, doi:10.2307/2289017, JSTOR 2289017, MR 0860518.
Plummer (1993). Plummer, Michael D. (1993), "Well-covered graphs: a survey", Quaestiones Mathematicae, 16 (3): 253–287, doi:10.1080/16073606.1993.9631737, MR 1254158, archived from the original on May 27, 2012.
Cook (1985). Cook, Stephen A. (1985), "A taxonomy of problems with fast parallel algorithms", Information and Control, 64 (1–3): 2–22, doi:10.1016/S0019-9958(85)80041-3, MR 0837088.
E.g., see Downey & Fellows (1995). Downey, R. G.; Fellows, M. R. (1995), "Fixed-parameter tractability and completeness. II. On completeness for W[1]", Theoretical Computer Science, 141 (1–2): 109–131, doi:10.1016/0304-3975(94)00097-3.
Itai & Rodeh (1978) provide an algorithm with $O (m 3/2)$ running time that finds a triangle if one exists but does not list all triangles; Chiba & Nishizeki (1985) list all triangles in time $O (m 3/2)$ . Itai, A.; Rodeh, M. (1978), "Finding a minimum circuit in a graph", SIAM Journal on Computing, 7 (4): 413–423, doi:10.1137/0207033. Chiba, N.; Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing, 14 (1): 210–223, doi:10.1137/0214017.
Eisenbrand & Grandoni (2004); Kloks, Kratsch & Müller (2000); Nešetřil & Poljak (1985); Vassilevska & Williams (2009); Yuster (2006). Eisenbrand, F.; Grandoni, F. (2004), "On the complexity of fixed parameter clique and dominating set", Theoretical Computer Science, 326 (1–3): 57–67, doi:10.1016/j.tcs.2004.05.009. Kloks, T.; Kratsch, D.; Müller, H. (2000), "Finding and counting small induced subgraphs efficiently", Information Processing Letters, 74 (3–4): 115–121, doi:10.1016/S0020-0190(00)00047-8. Nešetřil, J.; Poljak, S. (1985), "On the complexity of the subgraph problem", Commentationes Mathematicae Universitatis Carolinae, 26 (2): 415–419. Vassilevska, V.; Williams, R. (2009), "Finding, minimizing, and counting weighted subgraphs", Proc. 41st ACM Symposium on Theory of Computing, pp. 455–464, doi:10.1145/1536414.1536477, ISBN 978-1-60558-506-2. Yuster, R. (2006), "Finding and counting cliques and independent sets in r-uniform hypergraphs", Information Processing Letters, 99 (4): 130–134, doi:10.1016/j.ipl.2006.04.005.
Tomita, Tanaka & Takahashi (2006). Tomita, E.; Tanaka, A.; Takahashi, H. (2006), "The worst-case time complexity for generating all maximal cliques and computational experiments", Theoretical Computer Science, 363 (1): 28–42, doi:10.1016/j.tcs.2006.06.015.
Cazals & Karande (2008); Eppstein, Löffler & Strash (2013). Cazals, F.; Karande, C. (2008), "A note on the problem of reporting maximal cliques", Theoretical Computer Science, 407 (1): 564–568, doi:10.1016/j.tcs.2008.05.010. Eppstein, David; Löffler, Maarten; Strash, Darren (2013), "Listing all maximal cliques in large sparse real-world graphs in near-optimal time", Journal of Experimental Algorithmics, 18 (3): 3.1, arXiv:1103.0318, doi:10.1145/2543629.
Eppstein, Löffler & Strash (2013). Eppstein, David; Löffler, Maarten; Strash, Darren (2013), "Listing all maximal cliques in large sparse real-world graphs in near-optimal time", Journal of Experimental Algorithmics, 18 (3): 3.1, arXiv:1103.0318, doi:10.1145/2543629.
Balas & Yu (1986); Carraghan & Pardalos (1990); Pardalos & Rogers (1992); Östergård (2002); Fahle (2002); Tomita & Seki (2003); Tomita & Kameda (2007); Konc & Janežič (2007). Balas, E.; Yu, C. S. (1986), "Finding a maximum clique in an arbitrary graph", SIAM Journal on Computing, 15 (4): 1054–1068, doi:10.1137/0215075. Carraghan, R.; Pardalos, P. M. (1990), "An exact algorithm for the maximum clique problem", Operations Research Letters, 9 (6): 375–382, doi:10.1016/0167-6377(90)90057-C. Pardalos, P. M.; Rogers, G. P. (1992), "A branch and bound algorithm for the maximum clique problem", Computers & Operations Research, 19 (5): 363–375, doi:10.1016/0305-0548(92)90067-F. Östergård, P. R. J. (2002), "A fast algorithm for the maximum clique problem", Discrete Applied Mathematics, 120 (1–3): 197–207, doi:10.1016/S0166-218X(01)00290-6. Fahle, T. (2002), "Simple and fast: Improving a branch-and-bound algorithm for maximum clique", Proc. 10th European Symposium on Algorithms, Lecture Notes in Computer Science, vol. 2461, Springer-Verlag, pp. 47–86, doi:10.1007/3-540-45749-6_44, ISBN 978-3-540-44180-9. Tomita, E.; Seki, T. (2003), "An efficient branch-and-bound algorithm for finding a maximum clique", Discrete Mathematics and Theoretical Computer Science, Lecture Notes in Computer Science, vol. 2731, Springer-Verlag, pp. 278–289, doi:10.1007/3-540-45066-1_22, ISBN 978-3-540-40505-4. Tomita, E.; Kameda, T. (2007), "An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments", Journal of Global Optimization, 37 (1): 95–111, doi:10.1007/s10898-006-9039-7. Konc, J.; Janežič, D. (2007), "An improved branch and bound algorithm for the maximum clique problem" (PDF), MATCH Communications in Mathematical and in Computer Chemistry, 58 (3): 569–590. Source code
Battiti & Protasi (2001); Katayama, Hamamoto & Narihisa (2005). Battiti, R.; Protasi, M. (2001), "Reactive local search for the maximum clique problem", Algorithmica, 29 (4): 610–637, doi:10.1007/s004530010074. Katayama, K.; Hamamoto, A.; Narihisa, H. (2005), "An effective local search for the maximum clique problem", Information Processing Letters, 95 (5): 503–511, doi:10.1016/j.ipl.2005.05.010.
Abello, Pardalos & Resende (1999); Grosso, Locatelli & Della Croce (2004). Abello, J.; Pardalos, P. M.; Resende, M. G. C. (1999), "On maximum clique problems in very large graphs" (PDF), in Abello, J.; Vitter, J. (eds.), External Memory Algorithms, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol. 50, American Mathematical Society, pp. 119–130, ISBN 0-8218-1184-3, archived from the original (PDF) on 2017-01-16, retrieved 2017-01-13. Grosso, A.; Locatelli, M.; Della Croce, F. (2004), "Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem", Journal of Heuristics, 10 (2): 135–152, doi:10.1023/B:HEUR.0000026264.51747.7f.
Régin (2003). Régin, J.-C. (2003), "Using constraint programming to solve the maximum clique problem", Proc. 9th Int. Conf. Principles and Practice of Constraint Programming – CP 2003, Lecture Notes in Computer Science, vol. 2833, Springer-Verlag, pp. 634–648, doi:10.1007/978-3-540-45193-8_43, ISBN 978-3-540-20202-8.
Ouyang et al. (1997). Although the title refers to maximal cliques, the problem this paper solves is actually the maximum clique problem. Ouyang, Q.; Kaplan, P. D.; Liu, S.; Libchaber, A. (1997), "DNA solution of the maximal clique problem", Science, 278 (5337): 446–449, Bibcode:1997Sci...278..446O, doi:10.1126/science.278.5337.446, PMID 9334300.
Childs et al. (2002). Childs, A. M.; Farhi, E.; Goldstone, J.; Gutmann, S. (2002), "Finding cliques by quantum adiabatic evolution", Quantum Information and Computation, 2 (3): 181–191, arXiv:quant-ph/0012104, Bibcode:2000quant.ph.12104C, doi:10.26421/QIC2.3.
Even, Pnueli & Lempel (1972). Even, S.; Pnueli, A.; Lempel, A. (1972), "Permutation graphs and transitive graphs", Journal of the ACM, 19 (3): 400–410, doi:10.1145/321707.321710.
Blair & Peyton (1993), Lemma 4.5, p. 19. Blair, Jean R. S.; Peyton, Barry (1993), "An introduction to chordal graphs and clique trees", Graph theory and sparse matrix computation, IMA Vol. Math. Appl., vol. 56, Springer, New York, pp. 1–29, doi:10.1007/978-1-4613-8369-7_1, ISBN 978-1-4613-8371-0, MR 1320296.
Gavril (1973); Golumbic (1980), p. 247. Gavril, F. (1973), "Algorithms for a maximum clique and a maximum independent set of a circle graph", Networks, 3 (3): 261–273, doi:10.1002/net.3230030305. Golumbic, M. C. (1980), Algorithmic Graph Theory and Perfect Graphs, Computer Science and Applied Mathematics, Academic Press, ISBN 0-444-51530-5.
Clark, Colbourn & Johnson (1990). Clark, Brent N.; Colbourn, Charles J.; Johnson, David S. (1990), "Unit disk graphs", Discrete Mathematics, 86 (1–3): 165–177, doi:10.1016/0012-365X(90)90358-O
Song (2015). Song, Y. (2015), "On the independent set problem in random graphs", International Journal of Computer Mathematics, 92 (11): 2233–2242, doi:10.1080/00207160.2014.976210.
Jerrum (1992). Jerrum, M. (1992), "Large cliques elude the Metropolis process", Random Structures and Algorithms, 3 (4): 347–359, doi:10.1002/rsa.3240030402.
Alon, Krivelevich & Sudakov (1998). Alon, N.; Krivelevich, M.; Sudakov, B. (1998), "Finding a large hidden clique in a random graph", Random Structures & Algorithms, 13 (3–4): 457–466, doi:10.1002/(SICI)1098-2418(199810/12)13:3/4<457::AID-RSA14>3.0.CO;2-W.
Feige & Krauthgamer (2000). Feige, U.; Krauthgamer, R. (2000), "Finding and certifying a large hidden clique in a semirandom graph", Random Structures and Algorithms, 16 (2): 195–208, doi:10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A.
Meka, Potechin & Wigderson (2015). Meka, Raghu; Potechin, Aaron; Wigderson, Avi (2015), "Sum-of-squares lower bounds for planted clique", Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC '15), New York, NY, USA: ACM, pp. 87–96, arXiv:1503.06447, doi:10.1145/2746539.2746600, ISBN 978-1-4503-3536-2.
Boppana & Halldórsson (1992); Feige (2004); Halldórsson (2000). Boppana, R.; Halldórsson, M. M. (1992), "Approximating maximum independent sets by excluding subgraphs", BIT Numerical Mathematics, 32 (2): 180–196, doi:10.1007/BF01994876. Feige, U. (2004), "Approximating maximum clique by removing subgraphs", SIAM Journal on Discrete Mathematics, 18 (2): 219–225, doi:10.1137/S089548010240415X. Halldórsson, M. M. (2000), "Approximations of Weighted Independent Set and Hereditary Subset Problems", Journal of Graph Algorithms and Applications, 4 (1): 1–16, doi:10.7155/jgaa.00020.
Liu et al. (2015): "In terms of the number of vertices in graphs, Feige shows the currently known best approximation ratio". Liu et al. are writing about the maximum independent set but for purposes of approximation there is no difference between the two problems. Liu, Yu; Lu, Jiaheng; Yang, Hua; Xiao, Xiaokui; Wei, Zhewei (2015), "Towards maximum independent sets on massive graphs", Proceedings of the 41st International Conference on Very Large Data Bases (VLDB 2015) (PDF), Proceedings of the VLDB Endowment, vol. 8, pp. 2122–2133, doi:10.14778/2831360.2831366, hdl:10138/157292.
Cook (1971). Cook, S. A. (1971), "The complexity of theorem-proving procedures", Proc. 3rd ACM Symposium on Theory of Computing, pp. 151–158, doi:10.1145/800157.805047.
Cook (1971) gives essentially the same reduction, from 3-SAT instead of Satisfiability, to show that subgraph isomorphism is NP-complete. Cook, S. A. (1971), "The complexity of theorem-proving procedures", Proc. 3rd ACM Symposium on Theory of Computing, pp. 151–158, doi:10.1145/800157.805047.
Lipton & Tarjan (1980). Lipton, R. J.; Tarjan, R. E. (1980), "Applications of a planar separator theorem", SIAM Journal on Computing, 9 (3): 615–627, doi:10.1137/0209046.
Impagliazzo, Paturi & Zane (2001). Impagliazzo, R.; Paturi, R.; Zane, F. (2001), "Which problems have strongly exponential complexity?", Journal of Computer and System Sciences, 63 (4): 512–530, doi:10.1006/jcss.2001.1774.
Alon & Boppana (1987). For earlier and weaker bounds on monotone circuits for the clique problem, see Valiant (1983) and Razborov (1985). Alon, N.; Boppana, R. (1987), "The monotone circuit complexity of boolean functions", Combinatorica, 7 (1): 1–22, doi:10.1007/BF02579196. Valiant, L. G. (1983), "Exponential lower bounds for restricted monotone circuits", Proc. 15th ACM Symposium on Theory of Computing, pp. 110–117, doi:10.1145/800061.808739, ISBN 0-89791-099-0. Razborov, A. A. (1985), "Lower bounds for the monotone complexity of some Boolean functions", Proceedings of the USSR Academy of Sciences (in Russian), 281: 798–801. English translation in Sov. Math. Dokl. 31 (1985): 354–357{{citation}}: CS1 maint: postscript (link).
Amano & Maruoka (2005). Amano, Kazuyuki; Maruoka, Akira (2005), "A superpolynomial lower bound for a circuit computing the clique function with at most $(1/6)\log \log N$ negation gates", SIAM Journal on Computing, 35 (1): 201–216, doi:10.1137/S0097539701396959, MR 2178806.
Goldmann & Håstad (1992) used communication complexity to prove this result. Goldmann, M.; Håstad, J. (1992), "A simple lower bound for monotone clique using a communication game" (PDF), Information Processing Letters, 41 (4): 221–226, doi:10.1016/0020-0190(92)90184-W.
Wegener (1988). Wegener, I. (1988), "On the complexity of branching programs and decision trees for clique functions", Journal of the ACM, 35 (2): 461–472, doi:10.1145/42282.46161.
Childs & Eisenberg (2005); Magniez, Santha & Szegedy (2007). Childs, A. M.; Eisenberg, J. M. (2005), "Quantum algorithms for subset finding", Quantum Information and Computation, 5 (7): 593–604, arXiv:quant-ph/0311038, Bibcode:2003quant.ph.11038C, doi:10.26421/QIC5.7. Magniez, Frédéric; Santha, Miklos; Szegedy, Mario (2007), "Quantum algorithms for the triangle problem", SIAM Journal on Computing, 37 (2): 413–424, arXiv:quant-ph/0310134, doi:10.1137/050643684.
Downey & Fellows (1995). Downey, R. G.; Fellows, M. R. (1995), "Fixed-parameter tractability and completeness. II. On completeness for W[1]", Theoretical Computer Science, 141 (1–2): 109–131, doi:10.1016/0304-3975(94)00097-3.
Chen et al. (2006). Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge (2006), "Strong computational lower bounds via parameterized complexity", Journal of Computer and System Sciences, 72 (8): 1346–1367, doi:10.1016/j.jcss.2006.04.007
Feige et al. (1991); Arora & Safra (1998); Arora et al. (1998). Feige, U.; Goldwasser, S.; Lovász, L.; Safra, S; Szegedy, M. (1991), "Approximating clique is almost NP-complete", [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, pp. 2–12, doi:10.1109/SFCS.1991.185341, ISBN 0-8186-2445-0. Arora, S.; Safra, S. (1998), "Probabilistic checking of proofs: A new characterization of NP", Journal of the ACM, 45 (1): 70–122, doi:10.1145/273865.273901. Originally presented at the 1992 Symposium on Foundations of Computer Science, doi:10.1109/SFCS.1992.267824. Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), "Proof verification and the hardness of approximation problems", Journal of the ACM, 45 (3): 501–555, doi:10.1145/278298.278306, ECCC TR98-008. Originally presented at the 1992 Symposium on Foundations of Computer Science, doi:10.1109/SFCS.1992.267823.
Håstad (1999) showed inapproximability for this ratio using a stronger complexity theoretic assumption, the inequality of NP and ZPP. Khot (2001) described more precisely the inapproximability ratio, but with an even stronger assumption. Zuckerman (2006) derandomized the construction weakening its assumption to P ≠ NP. Håstad, J. (1999), "Clique is hard to approximate within $n^{1-\varepsilon }$ ", Acta Mathematica, 182 (1): 105–142, doi:10.1007/BF02392825. Khot, S. (2001), "Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring", Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 600–609, doi:10.1109/SFCS.2001.959936, ISBN 0-7695-1116-3. Zuckerman, D. (2006), "Linear degree extractors and the inapproximability of max clique and chromatic number", Proc. 38th ACM Symp. Theory of Computing, pp. 681–690, doi:10.1145/1132516.1132612, ISBN 1-59593-134-1, ECCC TR05-100.
This reduction is originally due to Feige et al. (1991) and used in all subsequent inapproximability proofs; the proofs differ in the strengths and details of the probabilistically checkable proof systems that they rely on. Feige, U.; Goldwasser, S.; Lovász, L.; Safra, S; Szegedy, M. (1991), "Approximating clique is almost NP-complete", [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, pp. 2–12, doi:10.1109/SFCS.1991.185341, ISBN 0-8186-2445-0.

dtic.mil (Global: 934^th place; English: 530^th place)

handle.dtic.mil

Plummer (1993). Plummer, Michael D. (1993), "Well-covered graphs: a survey", Quaestiones Mathematicae, 16 (3): 253–287, doi:10.1080/16073606.1993.9631737, MR 1254158, archived from the original on May 27, 2012.

hdl.handle.net (Global: 66^th place; English: 34^th place)

Liu et al. (2015): "In terms of the number of vertices in graphs, Feige shows the currently known best approximation ratio". Liu et al. are writing about the maximum independent set but for purposes of approximation there is no difference between the two problems. Liu, Yu; Lu, Jiaheng; Yang, Hua; Xiao, Xiaokui; Wei, Zhewei (2015), "Towards maximum independent sets on massive graphs", Proceedings of the 41st International Conference on Very Large Data Bases (VLDB 2015) (PDF), Proceedings of the VLDB Endowment, vol. 8, pp. 2122–2133, doi:10.14778/2831360.2831366, hdl:10138/157292.

inria.fr (Global: 6,372^nd place; English: 5,582^nd place)

hal.inria.fr

Rosgen & Stewart (2007). Rosgen, B; Stewart, L (2007), "Complexity results on graphs with few cliques", Discrete Mathematics and Theoretical Computer Science, 9 (1): 127–136.

insilab.org (Global: low place; English: low place)

Balas & Yu (1986); Carraghan & Pardalos (1990); Pardalos & Rogers (1992); Östergård (2002); Fahle (2002); Tomita & Seki (2003); Tomita & Kameda (2007); Konc & Janežič (2007). Balas, E.; Yu, C. S. (1986), "Finding a maximum clique in an arbitrary graph", SIAM Journal on Computing, 15 (4): 1054–1068, doi:10.1137/0215075. Carraghan, R.; Pardalos, P. M. (1990), "An exact algorithm for the maximum clique problem", Operations Research Letters, 9 (6): 375–382, doi:10.1016/0167-6377(90)90057-C. Pardalos, P. M.; Rogers, G. P. (1992), "A branch and bound algorithm for the maximum clique problem", Computers & Operations Research, 19 (5): 363–375, doi:10.1016/0305-0548(92)90067-F. Östergård, P. R. J. (2002), "A fast algorithm for the maximum clique problem", Discrete Applied Mathematics, 120 (1–3): 197–207, doi:10.1016/S0166-218X(01)00290-6. Fahle, T. (2002), "Simple and fast: Improving a branch-and-bound algorithm for maximum clique", Proc. 10th European Symposium on Algorithms, Lecture Notes in Computer Science, vol. 2461, Springer-Verlag, pp. 47–86, doi:10.1007/3-540-45749-6_44, ISBN 978-3-540-44180-9. Tomita, E.; Seki, T. (2003), "An efficient branch-and-bound algorithm for finding a maximum clique", Discrete Mathematics and Theoretical Computer Science, Lecture Notes in Computer Science, vol. 2731, Springer-Verlag, pp. 278–289, doi:10.1007/3-540-45066-1_22, ISBN 978-3-540-40505-4. Tomita, E.; Kameda, T. (2007), "An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments", Journal of Global Optimization, 37 (1): 95–111, doi:10.1007/s10898-006-9039-7. Konc, J.; Janežič, D. (2007), "An improved branch and bound algorithm for the maximum clique problem" (PDF), MATCH Communications in Mathematical and in Computer Chemistry, 58 (3): 569–590. Source code

jstor.org (Global: 23^rd place; English: 15^th place)

Day & Sankoff (1986). Day, William H. E.; Sankoff, David (1986), "Computational complexity of inferring phylogenies by compatibility", Systematic Zoology, 35 (2): 224–229, doi:10.2307/2413432, JSTOR 2413432.
Frank & Strauss (1986). Frank, Ove; Strauss, David (1986), "Markov graphs", Journal of the American Statistical Association, 81 (395): 832–842, doi:10.2307/2289017, JSTOR 2289017, MR 0860518.
See, e.g., Frank & Strauss (1986). Frank, Ove; Strauss, David (1986), "Markov graphs", Journal of the American Statistical Association, 81 (395): 832–842, doi:10.2307/2289017, JSTOR 2289017, MR 0860518.

kth.se (Global: low place; English: low place)

csc.kth.se

Goldmann & Håstad (1992) used communication complexity to prove this result. Goldmann, M.; Håstad, J. (1992), "A simple lower bound for monotone clique using a communication game" (PDF), Information Processing Letters, 41 (4): 221–226, doi:10.1016/0020-0190(92)90184-W.

labri.fr (Global: low place; English: low place)

Robson (2001). Robson, J. M. (2001), Finding a maximum independent set in time $O(2^{n/4})$ .

mgvis.com (Global: low place; English: low place)

Abello, Pardalos & Resende (1999); Grosso, Locatelli & Della Croce (2004). Abello, J.; Pardalos, P. M.; Resende, M. G. C. (1999), "On maximum clique problems in very large graphs" (PDF), in Abello, J.; Vitter, J. (eds.), External Memory Algorithms, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol. 50, American Mathematical Society, pp. 119–130, ISBN 0-8218-1184-3, archived from the original (PDF) on 2017-01-16, retrieved 2017-01-13. Grosso, A.; Locatelli, M.; Della Croce, F. (2004), "Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem", Journal of Heuristics, 10 (2): 135–152, doi:10.1023/B:HEUR.0000026264.51747.7f.

nih.gov (Global: 5^th place; English: 5^th place)

pubmed.ncbi.nlm.nih.gov

Rhodes et al. (2003). Rhodes, Nicholas; Willett, Peter; Calvet, Alain; Dunbar, James B.; Humblet, Christine (2003), "CLIP: similarity searching of 3D databases using clique detection", Journal of Chemical Information and Computer Sciences, 43 (2): 443–448, doi:10.1021/ci025605o, PMID 12653507.
Samudrala & Moult (1998). Samudrala, Ram; Moult, John (1998), "A graph-theoretic algorithm for comparative modeling of protein structure", Journal of Molecular Biology, 279 (1): 287–302, doi:10.1006/jmbi.1998.1689, PMID 9636717.
Spirin & Mirny (2003). Spirin, Victor; Mirny, Leonid A. (2003), "Protein complexes and functional modules in molecular networks", Proceedings of the National Academy of Sciences, 100 (21): 12123–12128, Bibcode:2003PNAS..10012123S, doi:10.1073/pnas.2032324100, PMC 218723, PMID 14517352.
Ouyang et al. (1997). Although the title refers to maximal cliques, the problem this paper solves is actually the maximum clique problem. Ouyang, Q.; Kaplan, P. D.; Liu, S.; Libchaber, A. (1997), "DNA solution of the maximal clique problem", Science, 278 (5337): 446–449, Bibcode:1997Sci...278..446O, doi:10.1126/science.278.5337.446, PMID 9334300.

ncbi.nlm.nih.gov

Spirin & Mirny (2003). Spirin, Victor; Mirny, Leonid A. (2003), "Protein complexes and functional modules in molecular networks", Proceedings of the National Academy of Sciences, 100 (21): 12123–12128, Bibcode:2003PNAS..10012123S, doi:10.1073/pnas.2032324100, PMC 218723, PMID 14517352.

rutgers.edu (Global: 2,011^th place; English: 1,139^th place)

dimacs.rutgers.edu

Johnson & Trick (1996). Johnson, D. S.; Trick, M. A., eds. (1996), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11–13, 1993, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26, American Mathematical Society, ISBN 0-8218-6609-5.
DIMACS challenge graphs for the clique problem Archived 2018-03-30 at the Wayback Machine, accessed 2009-12-17.

u-szeged.hu (Global: 9,326^th place; English: low place)

inf.u-szeged.hu

For instance, this follows from Gröger (1992). Gröger, Hans Dietmar (1992), "On the randomized complexity of monotone graph properties" (PDF), Acta Cybernetica, 10 (3): 119–127, archived from the original (PDF) on 2015-09-24, retrieved 2009-10-02

unt.edu (Global: 1,621^st place; English: 852^nd place)

digital.library.unt.edu

National Research Council Committee on Mathematical Challenges from Computational Chemistry (1995). See in particular pp. 35–36. National Research Council Committee on Mathematical Challenges from Computational Chemistry (1995), Mathematical Challenges from Theoretical/Computational Chemistry, National Academies Press, Bibcode:1995nap..book.4886N, doi:10.17226/4886, ISBN 978-0-309-05097-5.
Blair & Peyton (1993), Lemma 4.5, p. 19. Blair, Jean R. S.; Peyton, Barry (1993), "An introduction to chordal graphs and clique trees", Graph theory and sparse matrix computation, IMA Vol. Math. Appl., vol. 56, Springer, New York, pp. 1–29, doi:10.1007/978-1-4613-8369-7_1, ISBN 978-1-4613-8371-0, MR 1320296.

vldb.org (Global: low place; English: low place)

Liu et al. (2015): "In terms of the number of vertices in graphs, Feige shows the currently known best approximation ratio". Liu et al. are writing about the maximum independent set but for purposes of approximation there is no difference between the two problems. Liu, Yu; Lu, Jiaheng; Yang, Hua; Xiao, Xiaokui; Wei, Zhewei (2015), "Towards maximum independent sets on massive graphs", Proceedings of the 41st International Conference on Very Large Data Bases (VLDB 2015) (PDF), Proceedings of the VLDB Endowment, vol. 8, pp. 2122–2133, doi:10.14778/2831360.2831366, hdl:10138/157292.

web.archive.org (Global: 1^st place; English: 1^st place)

Plummer (1993). Plummer, Michael D. (1993), "Well-covered graphs: a survey", Quaestiones Mathematicae, 16 (3): 253–287, doi:10.1080/16073606.1993.9631737, MR 1254158, archived from the original on May 27, 2012.
Abello, Pardalos & Resende (1999); Grosso, Locatelli & Della Croce (2004). Abello, J.; Pardalos, P. M.; Resende, M. G. C. (1999), "On maximum clique problems in very large graphs" (PDF), in Abello, J.; Vitter, J. (eds.), External Memory Algorithms, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol. 50, American Mathematical Society, pp. 119–130, ISBN 0-8218-1184-3, archived from the original (PDF) on 2017-01-16, retrieved 2017-01-13. Grosso, A.; Locatelli, M.; Della Croce, F. (2004), "Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem", Journal of Heuristics, 10 (2): 135–152, doi:10.1023/B:HEUR.0000026264.51747.7f.
DIMACS challenge graphs for the clique problem Archived 2018-03-30 at the Wayback Machine, accessed 2009-12-17.
Karp (1972). Karp, Richard M. (1972), "Reducibility among combinatorial problems", in Miller, R. E.; Thatcher, J. W. (eds.), Complexity of Computer Computations (PDF), New York: Plenum, pp. 85–103, archived from the original (PDF) on 2011-06-29, retrieved 2009-12-17.
For instance, this follows from Gröger (1992). Gröger, Hans Dietmar (1992), "On the randomized complexity of monotone graph properties" (PDF), Acta Cybernetica, 10 (3): 119–127, archived from the original (PDF) on 2015-09-24, retrieved 2009-10-02

weizmann.ac.il (Global: 6,932^nd place; English: 9,400^th place)

eccc.weizmann.ac.il

Feige et al. (1991); Arora & Safra (1998); Arora et al. (1998). Feige, U.; Goldwasser, S.; Lovász, L.; Safra, S; Szegedy, M. (1991), "Approximating clique is almost NP-complete", [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, pp. 2–12, doi:10.1109/SFCS.1991.185341, ISBN 0-8186-2445-0. Arora, S.; Safra, S. (1998), "Probabilistic checking of proofs: A new characterization of NP", Journal of the ACM, 45 (1): 70–122, doi:10.1145/273865.273901. Originally presented at the 1992 Symposium on Foundations of Computer Science, doi:10.1109/SFCS.1992.267824. Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), "Proof verification and the hardness of approximation problems", Journal of the ACM, 45 (3): 501–555, doi:10.1145/278298.278306, ECCC TR98-008. Originally presented at the 1992 Symposium on Foundations of Computer Science, doi:10.1109/SFCS.1992.267823.
Håstad (1999) showed inapproximability for this ratio using a stronger complexity theoretic assumption, the inequality of NP and ZPP. Khot (2001) described more precisely the inapproximability ratio, but with an even stronger assumption. Zuckerman (2006) derandomized the construction weakening its assumption to P ≠ NP. Håstad, J. (1999), "Clique is hard to approximate within $n^{1-\varepsilon }$ ", Acta Mathematica, 182 (1): 105–142, doi:10.1007/BF02392825. Khot, S. (2001), "Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring", Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pp. 600–609, doi:10.1109/SFCS.2001.959936, ISBN 0-7695-1116-3. Zuckerman, D. (2006), "Linear degree extractors and the inapproximability of max clique and chromatic number", Proc. 38th ACM Symp. Theory of Computing, pp. 681–690, doi:10.1145/1132516.1132612, ISBN 1-59593-134-1, ECCC TR05-100.

zenodo.org (Global: 737^th place; English: 426^th place)

Song (2015). Song, Y. (2015), "On the independent set problem in random graphs", International Journal of Computer Mathematics, 92 (11): 2233–2242, doi:10.1080/00207160.2014.976210.

Clique problem (English Wikipedia)

4mhz.de (Global: low place; English: low place)

adsabs.harvard.edu (Global: 14th place; English: 9th place)

ui.adsabs.harvard.edu

ams.org (Global: 434th place; English: 249th place)

mathscinet.ams.org

archive.org (Global: 6th place; English: 6th place)

arxiv.org (Global: 49th place; English: 31st place)

berkeley.edu (Global: 621st place; English: 429th place)

cs.berkeley.edu

books.google.com (Global: 3rd place; English: 3rd place)

doi.org (Global: 2nd place; English: 2nd place)

dtic.mil (Global: 934th place; English: 530th place)

handle.dtic.mil

hdl.handle.net (Global: 66th place; English: 34th place)

inria.fr (Global: 6,372nd place; English: 5,582nd place)

hal.inria.fr

insilab.org (Global: low place; English: low place)

jstor.org (Global: 23rd place; English: 15th place)

kth.se (Global: low place; English: low place)

csc.kth.se

labri.fr (Global: low place; English: low place)

mgvis.com (Global: low place; English: low place)

nih.gov (Global: 5th place; English: 5th place)

pubmed.ncbi.nlm.nih.gov

ncbi.nlm.nih.gov

rutgers.edu (Global: 2,011th place; English: 1,139th place)

dimacs.rutgers.edu

u-szeged.hu (Global: 9,326th place; English: low place)

inf.u-szeged.hu

unt.edu (Global: 1,621st place; English: 852nd place)

digital.library.unt.edu

vldb.org (Global: low place; English: low place)

web.archive.org (Global: 1st place; English: 1st place)

weizmann.ac.il (Global: 6,932nd place; English: 9,400th place)

eccc.weizmann.ac.il

zenodo.org (Global: 737th place; English: 426th place)

adsabs.harvard.edu (Global: 14^th place; English: 9^th place)

ams.org (Global: 434^th place; English: 249^th place)

archive.org (Global: 6^th place; English: 6^th place)

arxiv.org (Global: 49^th place; English: 31^st place)

berkeley.edu (Global: 621^st place; English: 429^th place)

books.google.com (Global: 3^rd place; English: 3^rd place)

doi.org (Global: 2^nd place; English: 2^nd place)

dtic.mil (Global: 934^th place; English: 530^th place)

hdl.handle.net (Global: 66^th place; English: 34^th place)

inria.fr (Global: 6,372^nd place; English: 5,582^nd place)

jstor.org (Global: 23^rd place; English: 15^th place)

nih.gov (Global: 5^th place; English: 5^th place)

rutgers.edu (Global: 2,011^th place; English: 1,139^th place)

u-szeged.hu (Global: 9,326^th place; English: low place)

unt.edu (Global: 1,621^st place; English: 852^nd place)

web.archive.org (Global: 1^st place; English: 1^st place)

weizmann.ac.il (Global: 6,932^nd place; English: 9,400^th place)

zenodo.org (Global: 737^th place; English: 426^th place)