Clique problem (English Wikipedia)

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

refsWebsite

Global rank English rank

58doi.org

2^nd place

29semanticscholar.org

11^th place

8^th place

10ams.org

451^st place

277^th place

6arxiv.org

69^th place

59^th place

5web.archive.org

1^st place

5nih.gov

4^th place

4books.google.com

3^rd place

4harvard.edu

18^th place

17^th place

3psu.edu

207^th place

136^th place

3jstor.org

26^th place

20^th place

2unt.edu

1,336^th place

769^th place

2rutgers.edu

1,999^th place

1,355^th place

24mhz.de

low place

2weizmann.ac.il

4,983^rd place

8,002^nd place

1dtic.mil

833^rd place

567^th place

1inria.fr

4,903^rd place

3,679^th place

1labri.fr

low place

1archive.org

6^th place

1insilab.org

low place

1mgvis.com

low place

1zenodo.org

621^st place

380^th place

1vldb.org

low place

1handle.net

102^nd place

76^th place

1berkeley.edu

580^th place

462^nd place

1kth.se

low place

8,363^rd place

1u-szeged.hu

low place

4mhz.de

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, S2CID 7573663.
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, S2CID 7573663.

ams.org

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, S2CID 6390600. 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, S2CID 46153055.
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, S2CID 207051803.
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

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, S2CID 21436014. 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, S2CID 21436014. 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

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, S2CID 6390600. 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, S2CID 47515491.
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, S2CID 47515491.
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, S2CID 33643794.
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, S2CID 2754095.
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, S2CID 37556989. 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, S2CID 594494.

berkeley.edu

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

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, 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, 17: 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

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, S2CID 122923018.
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, 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, 17: 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, S2CID 12258606.
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, S2CID 6390600. 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, S2CID 118777692. 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, S2CID 46153055.
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, S2CID 118777692.
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, S2CID 207051803.
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, S2CID 207051803.
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, S2CID 207051803.
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, CiteSeerX 10.1.1.156.345, doi:10.1145/1536414.1536477, ISBN 978-1-60558-506-2, S2CID 224579. 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, S2CID 47515491.
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, S2CID 47515491.
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, S2CID 21436014. 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, S2CID 21436014. 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, S2CID 1800512. 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, S2CID 40764225.
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, S2CID 33643794.
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, S2CID 9501737.
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, S2CID 6713201.
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, S2CID 2754095.
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, S2CID 123335474. 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, S2CID 7573663.
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, S2CID 7573663.
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, S2CID 12961628.
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, S2CID 17397273. 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, S2CID 6326587. 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, CiteSeerX 10.1.1.185.3065, 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, S2CID 11967153.
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, S2CID 37556989. 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, S2CID 594494.
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, S2CID 46605913. 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, S2CID 751563. 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, S2CID 8561542, 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 - ε$ ", 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, S2CID 11987483. 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, S2CID 5713815, 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, S2CID 46605913.

dtic.mil

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.

handle.net

hdl.handle.net

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.

harvard.edu

ui.adsabs.harvard.edu

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, S2CID 33643794.
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, S2CID 37556989. 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, S2CID 594494.

inria.fr

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

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, S2CID 21436014. 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, S2CID 21436014. 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

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

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, CiteSeerX 10.1.1.185.3065, doi:10.1016/0020-0190(92)90184-W.

labri.fr

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

mgvis.com

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, S2CID 40764225.

nih.gov

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.

psu.edu

citeseerx.ist.psu.edu

Bomze et al. (1999); Gutin (2004). Bomze, I. M.; Budinich, M.; Pardalos, P. M.; Pelillo, M. (1999), "The maximum clique problem", Handbook of Combinatorial Optimization, vol. 4, Kluwer Academic Publishers, pp. 1–74, CiteSeerX 10.1.1.48.4074. Gutin, G. (2004), "5.3 Independent sets and cliques", in Gross, J. L.; Yellen, J. (eds.), Handbook of graph theory, Discrete Mathematics & Its Applications, CRC Press, pp. 389–402, ISBN 978-1-58488-090-5.
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, CiteSeerX 10.1.1.156.345, doi:10.1145/1536414.1536477, ISBN 978-1-60558-506-2, S2CID 224579. 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.
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, CiteSeerX 10.1.1.185.3065, doi:10.1016/0020-0190(92)90184-W.

rutgers.edu

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.

semanticscholar.org

api.semanticscholar.org

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, S2CID 122923018.
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, S2CID 12258606.
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, S2CID 6390600. 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, S2CID 118777692. 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, S2CID 46153055.
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, S2CID 118777692.
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, S2CID 207051803.
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, S2CID 207051803.
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, S2CID 207051803.
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, CiteSeerX 10.1.1.156.345, doi:10.1145/1536414.1536477, ISBN 978-1-60558-506-2, S2CID 224579. 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.
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, S2CID 47515491.
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, S2CID 47515491.
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, S2CID 21436014. 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, S2CID 21436014. 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, S2CID 1800512. 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, S2CID 40764225.
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, S2CID 33643794.
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, S2CID 9501737.
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, S2CID 6713201.
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, S2CID 2754095.
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, S2CID 123335474. 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.
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, S2CID 7573663.
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, S2CID 7573663.
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, S2CID 12961628.
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, S2CID 17397273. 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, S2CID 6326587. 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).
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, S2CID 11967153.
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, S2CID 37556989. 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, S2CID 594494.
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, S2CID 46605913. 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, S2CID 751563. 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, S2CID 8561542, 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 - ε$ ", 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, S2CID 11987483. 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, S2CID 5713815, 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, S2CID 46605913.

u-szeged.hu

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

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, 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

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

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, S2CID 40764225.
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

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, S2CID 46605913. 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, S2CID 751563. 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, S2CID 8561542, 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 - ε$ ", 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, S2CID 11987483. 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, S2CID 5713815, ECCC TR05-100.

zenodo.org

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, S2CID 6713201.