Problema clicii (Romanian Wikipedia)

Analysis of information sources in references of the Wikipedia article "Problema clicii" in Romanian language version.

refsWebsite

Global rank Romanian rank

58doi.org

2^nd place

3^rd place

10ams.org

451^st place

697^th place

5web.archive.org

1^st place

4nih.gov

4^th place

3jstor.org

26^th place

69^th place

3arxiv.org

69^th place

132^nd place

3wikidata.org

43^rd place

2^nd place

2books.google.com

3^rd place

6^th place

2nytimes.com

7^th place

25^th place

24mhz.de

low place

1psu.edu

207^th place

281^st place

1dtic.mil

833^rd place

2,488^th place

1inria.fr

4,903^rd place

low place

1labri.fr

low place

1insilab.org

low place

1mgvis.com

low place

1rintonpress.com

low place

1rutgers.edu

1,999^th place

1,623^rd place

1berkeley.edu

580^th place

396^th place

1u-szeged.hu

low place

1,917^th 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 .
Cook (1971) furnizează în esență aceeași reducere, din 3-SAT^⁠(d) în loc de satisfiabilitate, pentru a arăta că izomorfismul de subgraf^⁠(d) este NP-complet. 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 .

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 .
Graful Keller utilizat de Lagarias & Shor (1992) are 1048576 de noduri și mărimea clicii 1024. 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, doi:10.1090/S0273-0979-1992-00318-X, MR 1155280 .
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, arhivat din original la 27 mai 2012, accesat în 31 mai 2017 .
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., 56, Springer, New York, pp. 1–29, doi:10.1007/978-1-4613-8369-7_1, 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 .

arxiv.org

Childs et al. (2002). Childs, A. M.; Farhi, E.; Goldstone, J.; Gutmann, S. (2002), „Finding cliques by quantum adiabatic evolution” (PDF), Quantum Information and Computation, 2 (3): 181–191, arXiv:quant-ph/0012104  ^{[nefuncțională]}.
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  . 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

cs.berkeley.edu

Karp (1972). Karp, Richard M. (1972), „Reducibility among combinatorial problems”, În Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (PDF), New York: Plenum, pp. 85–103, arhivat din original (PDF) la 29 iunie 2011, accesat în 31 mai 2017 .

books.google.com

Wasserman & Faust (1994). Wasserman, Stanley; Faust, Katherine (1994), Social Network Analysis: Methods and Applications, Structural Analysis in the Social Sciences, 8, Cambridge University Press, p. 276, ISBN 978-0-521-38707-1 .
Skiena (2009), p. 526. Skiena, Steven S. (2009), The Algorithm Design Manual (ed. 2nd), 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 .
National Research Council Committee on Mathematical Challenges from Computational Chemistry (1995). National Research Council Committee on Mathematical Challenges from Computational Chemistry (1995), Mathematical Challenges from Theoretical/Computational Chemistry, National Academies Press, doi:10.17226/4886 .
Muegge & Rarey (2001). Muegge, Ingo; Rarey, Matthias (2001), „Small molecule docking and scoring”, Reviews in Computational Chemistry, 17: 1–60, doi:10.1002/0471224413.ch1 .
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 .
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, 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 .
Graful Keller utilizat de Lagarias & Shor (1992) are 1048576 de noduri și mărimea clicii 1024. 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, doi:10.1090/S0273-0979-1992-00318-X, MR 1155280 .
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 .
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 .
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, arhivat din original la 27 mai 2012, accesat în 31 mai 2017 .
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” (PDF), Theoretical Computer Science, 407 (1): 564–568, doi:10.1016/j.tcs.2008.05.010 ^{[nefuncțională]}. 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, 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, 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, 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, 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), În Abello, J.; Vitter, J., External Memory Algorithms, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, 50, American Mathematical Society, pp. 119–130, ISBN 0-8218-1184-3, arhivat din original (PDF) la 16 ianuarie 2017, accesat în 31 mai 2017 . 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, 2833, Springer-Verlag, pp. 634–648, doi:10.1007/978-3-540-45193-8_43 .
Ouyang et al. (1997). Ouyang, Q.; Kaplan, P. D.; Liu, S.; Libchaber, A. (1997), „DNA solution of the maximal clique problem”, Science, 278 (5337): 446–449, doi:10.1126/science.278.5337.446, PMID 9334300 .
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., 56, Springer, New York, pp. 1–29, doi:10.1007/978-1-4613-8369-7_1, 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, 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), Proceedings of the VLDB Endowment, 8 (13), pp. 2122–2133, doi:10.14778/2831360.2831366 .
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) furnizează în esență aceeași reducere, din 3-SAT^⁠(d) în loc de satisfiabilitate, pentru a arăta că izomorfismul de subgraf^⁠(d) este NP-complet. 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). Alon, N.; Boppana, R. (1987), „The monotone circuit complexity of boolean functions”, Combinatorica, 7 (1): 1–22, doi:10.1007/BF02579196 .
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^⁠(d) to prove this result. Goldmann, M.; Håstad, J. (1992), „A simple lower bound for monotone clique using a communication game”, 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  . 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
Kolata (1990); Feige et al. (1991); Arora & Safra (1998); Arora et al. (1998). Kolata, Gina (26 iunie 1990), „In a Frenzy, Math Enters Age of Electronic Mail”, New York Times . Feige, U.; Goldwasser, S.; Lovász, L.; Safra, S; Szegedy, M. (1991), „Approximating clique is almost NP-complete”, Proc. 32nd IEEE Symp. on 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, Format:ECCC . Originally presented at the 1992 Symposium on Foundations of Computer Science, doi:10.1109/SFCS.1992.267823.
Håstad (1999) a arătat neaproximabilitatea pentru acest raport folosind o ipoteză de complexitate mai puternică, inegalitatea între NP și ZPP^⁠(d). Håstad, J. (1999), „Clique is hard to approximate within $n 1 - ε$ ”, Acta Mathematica, 182 (1): 105–142, doi:10.1007/BF02392825 .
Această reducere li se datorează lui Feige et al. (1991) și este utilizată în toate demonstrațiile ulterioare de neaproximabilitate; demonstrațiile diferă în puterea și în detaliile sistemului de demonstrații verificabile probabilistic pe care se bazează. Feige, U.; Goldwasser, S.; Lovász, L.; Safra, S; Szegedy, M. (1991), „Approximating clique is almost NP-complete”, Proc. 32nd IEEE Symp. on Foundations of Computer Science, pp. 2–12, doi:10.1109/SFCS.1991.185341, ISBN 0-8186-2445-0 .

dx.doi.org

Kolata (1990); Feige et al. (1991); Arora & Safra (1998); Arora et al. (1998). Kolata, Gina (26 iunie 1990), „In a Frenzy, Math Enters Age of Electronic Mail”, New York Times . Feige, U.; Goldwasser, S.; Lovász, L.; Safra, S; Szegedy, M. (1991), „Approximating clique is almost NP-complete”, Proc. 32nd IEEE Symp. on 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, Format:ECCC . Originally presented at the 1992 Symposium on Foundations of Computer Science, doi:10.1109/SFCS.1992.267823.

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, arhivat din original la 27 mai 2012, accesat în 31 mai 2017 .

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

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 .

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), În Abello, J.; Vitter, J., External Memory Algorithms, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, 50, American Mathematical Society, pp. 119–130, ISBN 0-8218-1184-3, arhivat din original (PDF) la 16 ianuarie 2017, accesat în 31 mai 2017 . 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

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, doi:10.1073/pnas.2032324100, PMC 218723 , PMID 14517352 .
Ouyang et al. (1997). Ouyang, Q.; Kaplan, P. D.; Liu, S.; Libchaber, A. (1997), „DNA solution of the maximal clique problem”, Science, 278 (5337): 446–449, doi:10.1126/science.278.5337.446, PMID 9334300 .

nytimes.com

Kolata (1990). Kolata, Gina (26 iunie 1990), „In a Frenzy, Math Enters Age of Electronic Mail”, New York Times .
Kolata (1990); Feige et al. (1991); Arora & Safra (1998); Arora et al. (1998). Kolata, Gina (26 iunie 1990), „In a Frenzy, Math Enters Age of Electronic Mail”, New York Times . Feige, U.; Goldwasser, S.; Lovász, L.; Safra, S; Szegedy, M. (1991), „Approximating clique is almost NP-complete”, Proc. 32nd IEEE Symp. on 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, Format:ECCC . Originally presented at the 1992 Symposium on Foundations of Computer Science, doi:10.1109/SFCS.1992.267823.

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, 4, Kluwer Academic Publishers, pp. 1–74, CiteSeerX 10.1.1.48.4074  . Gutin, G. (2004), „5.3 Independent sets and cliques”, În Gross, J. L.; Yellen, J., Handbook of graph theory, Discrete Mathematics & Its Applications, CRC Press, pp. 389–402, ISBN 978-1-58488-090-5 .

rintonpress.com

Childs et al. (2002). Childs, A. M.; Farhi, E.; Goldstone, J.; Gutmann, S. (2002), „Finding cliques by quantum adiabatic evolution” (PDF), Quantum Information and Computation, 2 (3): 181–191, arXiv:quant-ph/0012104  ^{[nefuncțională]}.

rutgers.edu

dimacs.rutgers.edu

Johnson & Trick (1996). Johnson, D. S.; Trick, M. A., ed. (1996), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11–13, 1993, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 26, American Mathematical Society, ISBN 0-8218-6609-5 .

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, arhivat din original (PDF) la 24 septembrie 2015, accesat în 2 octombrie 2009

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, arhivat din original la 27 mai 2012, accesat în 31 mai 2017 .
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), În Abello, J.; Vitter, J., External Memory Algorithms, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, 50, American Mathematical Society, pp. 119–130, ISBN 0-8218-1184-3, arhivat din original (PDF) la 16 ianuarie 2017, accesat în 31 mai 2017 . 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 Arhivat în 30 martie 2018, la Wayback Machine., accesat la 2009-12-17.
Karp (1972). Karp, Richard M. (1972), „Reducibility among combinatorial problems”, În Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (PDF), New York: Plenum, pp. 85–103, arhivat din original (PDF) la 29 iunie 2011, accesat în 31 mai 2017 .
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, arhivat din original (PDF) la 24 septembrie 2015, accesat în 2 octombrie 2009

wikidata.org

Cook (1971) furnizează în esență aceeași reducere, din 3-SAT^⁠(d) în loc de satisfiabilitate, pentru a arăta că izomorfismul de subgraf^⁠(d) este NP-complet. 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 .
Goldmann & Håstad (1992) used communication complexity^⁠(d) to prove this result. Goldmann, M.; Håstad, J. (1992), „A simple lower bound for monotone clique using a communication game”, Information Processing Letters, 41 (4): 221–226, doi:10.1016/0020-0190(92)90184-W .
Håstad (1999) a arătat neaproximabilitatea pentru acest raport folosind o ipoteză de complexitate mai puternică, inegalitatea între NP și ZPP^⁠(d). Håstad, J. (1999), „Clique is hard to approximate within $n 1 - ε$ ”, Acta Mathematica, 182 (1): 105–142, doi:10.1007/BF02392825 .