Mostrar código-fonte de Problema do clique

Em [[ciência da computação]], o '''problema do clique''' refere-se a qualquer problema que possui como objetivo encontrar subgrafos completos ("[[clique]]s") em um [[grafo]]. Como exemplo, o problema de encontrar conjuntos de nós em que todos os elementos estão conectados entre si.

Por exemplo, o problema clique surge no cenário seguinte. Considere uma [[rede social]], onde os [[vértices]] do grafo representam pessoas, e as [[arestas]] representam o conhecimento mútuo. Para encontrar um maior subconjunto de pessoas, em que todas conhecem umas as outras, pode-se sistematicamente inspecionar todos os subconjuntos, um processo que é muito demorado para ser prático para as redes sociais, mesmo que pequenas. Embora a pesquisa por [[força bruta]] possa ser melhorada através de algoritmos mais eficientes, todos estes [[algoritmos]] levam tempo exponencial para resolver o problema. Portanto, grande parte da teoria sobre o '''problema do clique''' é dedicado à identificação de tipos especiais de gráfo que admitem algoritmos mais eficientes, ou a definição da dificuldade computacional do problema geral em vários modelos de computação. Junto com seus aplicativos em redes sociais , o clique também tem muitas aplicações em [[bioinformática]] e [[química computacional]].

Problemas que envolvem o clique:

*encontrar o clique máximo (um clique com o maior número de vértices);
*encontrar o clique com maior valor em um grafo valorado;
*listar todos os cliques máximos (cliques que não podem ser ampliados);
*resolver o [[problema de decisão]] de testar se um grafo contém um clique maior que um tamanho determinado.

	Esses problemas são todos difíceis: o problema de decisão clique é [[NP-completo]] (um dos 21 problemas [[NP-Completo]] de Karp), e listar todos os cliques máximos pode exigir tempo exponencial. No entanto, existem algoritmos para esses problemas que são executados em tempo exponencial ou que lidam com grafos de entrada mais especializados em tempo polinomial.

==História==
Embora subgrafos completos tenham sido estudados por mais tempo na [[matemática]], o termo "clique" e o problema da listagem de cliques algoritmicamente vêm das [[ciências sociais]], onde subgrafos completos são usados para modelar cliques sociais, grupos de pessoas que se conhecem. O termo "clique" vem de Luce & Perry (1949), e o primeiro [[algoritmo]] para resolver o problema clique foi demonstrado por Harary & Ross (1957), motivados pela aplicação sociológica.

Desde o trabalho de Harary e Ross, muitos outros criaram algoritmos para várias versões do problema clique. Na década de 1970, os pesquisadores começaram a estudar estes algoritmos do ponto de vista da análise de pior caso, ver, por exemplo, Tarjan & Trojanowski (1977), um trabalho inicial sobre a [[complexidade]] do pior caso do problema do clique máximo. Também na década de 1970, começando com o trabalho de Cook (1971) e Karp (1972), os pesquisadores começaram a encontrar justificativa matemática para a dificuldade percebida do problema clique na teoria da NP-completude e resultados relacionados com intratabilidade. Na década de 1990, uma série inovadora de artigos começando por Feige et al. (1991) e relatado na época nos principais jornais, mostrou que não é sequer possível aproximar o problema com precisão e eficiência.

==Definição==
Um grafo não-direcionado é formado por um conjunto finito de vértices e um conjunto de pares não ordenados de vértices, que são chamados de arestas. Por convenção, na análise de algoritmos, o número de vértices do grafo é denotado por n e o número de arestas é denotado por m. Um clique em um grafo G é um subgrafo completo de G, ou seja, é um subconjunto S de vértices tal que todo par de nós está conectado por uma aresta. Uma clique maximal é um clique para o qual não se pode mais adicionar vértices; um clique máximo é um clique que inclui o maior número possível de vértices em um grafo.

Vários problemas relacionados à busca de cliques em grafos já foram estudados:

*No problema do clique máximo, a entrada é um grafo não direcionado, e a saída é uma clique máximo no grafo. Se houver vários cliques máximos, apenas um precisa ser a saída.
*No problema do clique máximo com pesos, a entrada é um grafo não direcionado, com pesos em seus vértices (ou, menos frequentemente, arestas) e a saída é clique com peso total máximo. O problema do clique máximo é o caso especial em que todos os pesos são um.
*No problema k-clique, a entrada é um grafo não direcionado e um número k, e a saída é um clique de tamanho k, se existir um (ou, às vezes, todos os cliques de tamanho k).
*No problema de decisão de clique, a entrada é um grafo não direcionado e um número k, e a saída é um valor booliano: verdadeiro se o grafo contém um k-clique, e falso caso contrário.

	Os três primeiros destes problemas são todos importantes em aplicações práticas. Já o problema de decisão do clique é necessário para aplicar a teoria da NP-completude aos problemas de encontrar cliques em grafos.
	O problema do clique e o problema dos conjuntos independentes são complementares: um clique em G é um conjunto independente no grafo complementar de G e vice versa. Portanto, muitos resultados computacionais podem ser aplicados igualmente para ambos os problemas e algumas pesquisas não distinguem claramente a diferença entre esses dois problemas. Contudo,  os dois problemas têm diferentes propriedades quando aplicados a famílias restritas de grafos; por exemplo, o problema do clique pode ser resolvido em tempo polinomial para grafos planares enquanto  o problema de conjuntos independentes continua NP-difícil.

==Algoritmos==

===Maximal versus Máximo===
Um clique maximal, às vezes chamado de inclusão-maximal, é um clique que não é incluso em um clique maior. Encontrar um clique maximal é trivial: Começando do primeiro vértice, expanda o clique atual iterando sobre os vértices restantes do grafo, adicionar um vértice se ele está conectado a todos os outros vértices do clique atual. Esse algoritmo roda em tempo O(''m''). Contudo,  cliques maximais podem ser muito pequenos; Um grafo pode conter um clique de tamanho ''n''−1, mas um clique maximal de tamanho 2. Então, enquanto um máximo (ex., o maior) clique é necessariamente maximal, o inverso não se mantém, e a maior atenção dos algoritmos é dada ao problema muito mais difícil de achar um máximo.

===Cliques de tamanho fixo===
Um algoritmo de força bruta para testar se um grafo G contém um k-vertices clique, e achar qualquer clique que ele contém, é examinar cada subgrafo com pelo menos k verticies e checar se ele forma um clique. Esse algoritmo toma o tempo O(''n''<sup>''k''</sup>&nbsp;''k''<sup>2</sup>):  existem  O(''n''<sup>''k''</sup>) subgrafos para checar, cada um dos quais tem O(''k''<sup>2</sup>) arestas cuja presença em G precisa ser checada. Portanto, o problema pode ser resolvido em tempo polinomial quando k é uma constante fixa. Mas quando k é uma entrada para o problema o tempo é exponencial.
O caso não-trivial mais simples de problemas relacionados a achar o clique é achar um triangulo em um grafo, ou de forma análoga,  determinar se o grafo não contém nenhum triangulo. Em um grafo com m arestas, podem existir no máximo Θ(''m''<sup>3/2</sup>) triângulos; O pior caso ocorre quando G é um clique. Portanto, algoritmos para listar todos os triângulos devem tomar pelo menos o tempo Ω(''m''<sup>3/2</sup>) no pior caso, e são conhecidos algoritmos que seguem esse limite. Por exemplo  {{harvtxt|Chiba|Nishizeki|1985}} descrevem um algoritmo que ordena os vértices na ordem do maior grau pro menor e então itera sobre cada vértice v na lista ordenada, procurando por triângulos que incluem v e não incluem nenhum vértice numa posição anterior da lista.  Para fazê-lo o algoritmo marca todos os vizinhos de v, procura por todas as arestas incidentes a um vizinho de v retornando um triangulo para cada aresta que tem 2 pontos finais marcados, e então remove as marcas e deleta v do grafo. Como os autores mostram, o tempo para o algoritmo é proporcional a arboricidade do grafo(a(G)) vezes o número de arestas,  que é  O(''m''&nbsp;''a''(''G'')).  Já que a arboricidade é no máximo O(''m''<sup>1/2</sup>),  esse algoritmo roda em tempo O(''m''<sup>3/2</sup>).  Generalizando, todos os k-vertices cliques pode ser listados por um algoritmo similar que toma tempo proporcional ao número de arestas vezes (k-2)  ézima potencia da arboricidade. Para grafos de arboricidade constante, como grafos planares, esse algoritmo toma tempo O(''m'').

Se o objetivo é achar um único triangulo, ou a garantia que o grafo não possui nenhum, algoritmos mais rápidos são possíveis. Como {{harvtxt|Itai|Rodeh|1978}}  observou, o grafo contem um triangulo se e somente se a sua matriz de adjacência e o quadrado da matriz de adjacência contem uma quantidade diferentes de 0 de entradas na mesma célula; Portanto,  técnicas rápidas de multiplicação de matrizes como o algoritmo de Coppersmith–Winograd podem ser aplicadas para achar triângulos em tempo O(''n''<sup>2.376</sup>), o que pode ser mais rápido que O(''m''<sup>3/2</sup>)  para grafos suficientemente densos {{harvtxt|Alon|Yuster|Zwick|1994}}  melhorou o algoritmo de achar triângulos O(''m''<sup>3/2</sup>)  para  O(''m''<sup>1.41</sup>)  usando rápida multiplicação de matrizes. Essa ideia do uso de rápida multiplicação de matrizes para achar triângulos também foi estendida para problemas de achar k-cliques com valores maiores para k.

===Listando todos os cliques maximais===
Como um resultado de Moon & Moser (1965), qualquer n-vertice grafo tem no máximo 3<sup>''n''/3</sup> cliques maximais. O algoritmo de Bron–Kerbosch é um procedimento recursivo com  [[backtracking]] de {{harvtxt|Bron|Kerbosch|1973}} que modifica um clique candidato considerando um vértice por vez, ou adicionando ele ao clique candidato ou a um conjunto de vértices excluídos que não podem estar no clique, mas devem ter algum não-vizinho no eventual clique; variantes desse algoritmo tem o pior caso em tempo O(3<sup>''n''/3</sup>). Portanto isso prove uma solução de pior caso ótima para o problema de achar todos os conjuntos maximais independentes; O algoritmo de Bron–Kerbosch foi amplamente reportado como sendo mais rápido na pratica que suas alternativas.
Como {{harvtxt|Tsukiyama|Ide|Ariyoshi|Shirakawa|1977}}  mostrou, também é possível listar todos os cliques maximais em um grafo em um tempo que é polinomial por clique gerado. Um algoritmo como o dele na qual o tempo depende no tamanho da saída é conhecido como algoritmo sensível a saída. O algoritmo deles é baseado nas duas seguintes observações,  relacionando os cliques maximais do dado grafo G a os cliques maximais de um grafo G/ v formado pela remoção de um vértice arbitrário v de G:
*Para cada clique maximal C de G/v, ou C continua para formar um clique maximal em G, ou C  u {v} forma um clique maximal em G. Portanto, G tem pelo menos  tantos cliques maximais quanto G/v.
*Cada clique maximal em G que não contém v é um clique maximal em G/v, e cada clique maximal em G que contém v pode ser formado por um clique maximal C em G/v adicionando v e removendo os não-vizinhos de v que pertencem a C.
Usando essas observações eles podem gerar todos cliques maximais em G gerando um algoritmo recursivo que, para cada clique maximal C em G/v, retorna  C e o clique formado pela adição de v a C e removendo os não-vizinhos de v. Contudo, alguns cliques de G podem ser gerados dessa maneira a partir de mais de um clique parente de  G/v, então eles eliminam os repetidos  retornando um clique somente se o seu parente em G/v é lexicograficamente Maximo dentre todos os cliques parentes possíveis. Na base desse princípio, eles mostraram que todos os cliques maximais em G podem ser gerados em temp O(''mn'') por clique, onde m é o número de arestas em g e n é o número de vértices; {{harvtxt|Chiba|Nishizeki|1985}} melhorou esse tempo para O(ma) por clique, onde a é a arboricidade do dado grafo. {{harvtxt|Makino|Uno|2004}} prove uma alternativa para o algoritmo sensível a saída baseado em multiplicação rápida de matrizes, e and Johnson & Yannakakis (1988) mostrou que é possível listar todos os cliques maximais em ordem lexicográfica com delay polinomial por clique, apesar do inverso dessa ordem ser NP-hard para gerar.
Na base desse resultado, é possível listar todos os cliques maximais em tempo polinomial, para famílias de grafos  das quais o número de cliques é limitado polinomialmente. Essas famílias incluem grafos completos, grafos livres de triângulos, grafos de intervalo e grafos planares.

===Achando cliques máximos em grafos arbitrários===

É possível achar o clique máximo, ou o número do clique, de um grafo arbitrário com n vértices em tempo O(3<sup>''n''/3</sup>) = O(1.4422<sup>''n''</sup>) usando um dos algoritmos descritos acima para listar todos os cliques maximais e retornar o maior deles. Contudo, para essa variante do problema do clique,  melhores algoritmos de pior caso são possíveis. O algoritmo de Tarjan & Trojanowski (1977) resolve o problema em tempo O(2<sup>''n''/3</sup>) = O(1.2599<sup>''n''</sup>);  É um esquema recursivo com backtracking similar ao do algoritmo de Bron–Kerbosch, mas é capaz de eliminar algumas chamadas recursivas quando pode ser mostrado que algumas outras combinações de vértices não usados na chamada é garantia para levar a um solução pelo menos tão boa quanto a atual. {{harvtxt|Jian|1986}} melhorou esse tempo O(2<sup>0.304''n''</sup>) = O(1.2346<sup>''n''</sup>).  {{harvtxt|Robson|1986}} melhorou o anterior para  o tempo O(2<sup>0.276''n''</sup>) = O(1.2108<sup>''n''</sup>) ao custo de maior uso de espaço, com um esquema similar de backtracking com uma análise de caso mais complicada, junto com uma técnica de programação dinâmica na qual a solução ótima é pré computada para todos os pequenos subgrafos conectados do grafo complementar e essas soluções parciais são usadas como um atalho na recursão do backtracking. O algoritmo mais rápido conhecido atualmente é o de  {{harvtxt|Robson|2001}} que roda em tempo O(2<sup>0.249''n''</sup>) = O(1.1888<sup>''n''</sup>).

Também houve pesquisa extensiva em algoritmos heurísticos  para resolver problemas de clique máximo sem a garantia de runtime em pior caso, baseado em métodos incluindo branch and bound,  busca local, algoritmos gulosos e constraint programing. Metodologias incomuns de computação para achar cliques incluem computação em DNA e computação quântica adiabática. O problema do máximo clique foi assunto de um desafio de implementação patrocinado pelo DIMACS em 1992-1993, e uma coleção de grafos usados como benchmarks para o desafio está disponível publicamente.

===Casos especiais de grafos===
Grafos planares e outras famílias de grafos esparsos , foram discutidas acima: eles tem muitos cliques maximais, de tamanho limitado, que podem ser listados em tempo linear. Em particular, para grafos planares, qualquer clique pode ter no máximo 4 vértices, pelo teorema de Kuratowski's.

Grafos perfeitos são definidos pelas propriedades que o seu número de clique é igual ao seu número cromático, e que isso permanece verdade em cada um dos seus subgrafos induzidos. Para grafos perfeitos, é possível achar o clique máximo em tempo polinomial, usando um algoritmo baseado em Semidefinite programming. Contudo, esse método é complexo e não combinatório e algoritmos especializados em achar o clique foram desenvolvidos para muitas subclasses de grafos perfeitos. No complemento de grafos  bipartidos, o teorema de König's permite que o problema de clique máximo seja resolvido usando técnicas para matching. Em outra classe de grafos perfeitos, os grafos de permutação, o clique máximo é a mais longa sub sequência decrescente  da permutação definindo o grafo e pode ser achada usando algoritmos conhecidos para esse problema. Em grafos cordais, os clique maximais  são um subconjunto de um dos n cliques formados como parte de uma de ordem de eliminação.

Em alguns casos, esses algoritmos podem ser estendidos para outras, não perfeitas, classes de grafos: por exemplo, em um grafo circular, os vizinhos de cada vértice é um grafo de permutação, então o clique Maximo encontrado em um grafo circular pode ser achado usando o algoritmo para grafos de permutação para cada vizinho. Similarmente, em um unit disk graph(com uma representação geométrica conhecida), existe um algoritmo em tempo polinomial para cliques máximos baseado no algoritmo usado para o complemento de grafos bi partidos.

O problema algoritmo de achar o clique Maximo em um grafo aleatório desenhado a partir do modelo de Erdos–Rényi(no qual cada aresta aparece com uma probabilidade de ½ independente das outras) foi sugerido {{harvtxt|Karp|1976}}.  Apesar do número de clique de tais grafos ser muito próximo de 2&nbsp;log<sub>2</sub>''n'', tanto algoritmos gulosos mais simples quanto técnicas sofisticadas de aproximações aleatórias só  acham cliques com tamanho log<sub>2</sub>''n'',  e o número de cliques maximais em tais grafos tem alta probabilidade de ser exponenciais em log<sup>2</sup>''n'' prevenindo que exista um solução em tempo polinomial que liste todos eles. Por causa da dificuldade desse problema, muitos autores têm investigado variantes do problema na qual o grafo aleatório é modificado adicionando um grande clique, de tamanho proporcional a √''n''. É possível achar esse clique escondido com grande probabilidade em tempo polinomial, ou usando spectral methods ou semidefinite programing.

===Algoritmos de Aproximação===
Muitos autores têm considerado algoritmos de aproximação que tentam achar um clique ou um conjunto independente que, apesar de não ser o máximo, tem um tamanho o mais perto possível do máximo que pode ser encontrado em tempo polinomial. Apesar de que boa parte desse trabalho seja focado em conjuntos independentes em grafos esparsos, um caso que não faz sentido para o problema do clique complementar, também houve trabalho em algoritmos de aproximação que não usam a suposição de grafos esparsos.
{{harvtxt|Feige|2004}} descreve um algoritmo de tempo polinomial que acha um clique de tamanho Ω((log&nbsp;''n''/log&nbsp;log&nbsp;''n'')<sup>2</sup>) em qualquer grafo que tenho um número de clique  Ω(''n''/log<sup>''k''</sup>''n'') para qualquer constante k. Combinando esse algoritmo para achar cliques em grafos com números de clique entre ''n''/log&nbsp;''n'' e ''n''/log<sup>3</sup>''n'' com um algoritmo diferente de {{harvtxt|Boppana|Halldórsson|1992}} para achar cliques em grafos com número de clique maior, e escolhendo um clique de 2 vertices caso ambos os algoritmos falhem, Feige prove um algoritmo de  aproximação que acha o clique com um número de vertices dentro de um fator de  O(''n''(log&nbsp;log&nbsp;''n'')<sup>2</sup>/log<sup>3</sup>''n'') do máximo.

==Limites inferiores==

===NP-completude===
O problema                de decisão do clique é NP-completo. Foi um dos 21 problemas originais de Richard Karp’s mostrados no seu trabalho de 1972 “Reducibility Among Combinatorial Problems". Esse problema também foi mencionado no trabalho de Stephen Cook's introduzindo a teoria de problemas NP-completos. O problema de achar um clique máximo é NP-difícil:  Se o mesmo for resolvido, também é possível resolver o problema da decisão, comparando o tamanho do clique máximo com o tamanho do parâmetro dado com entrada do problema da decisão.

A prova da NP-completude de Karp é uma redução do problema SAT para formulas na forma normal conjuntiva,  o qual for provado NP-completo no teorema de Cook-levin. Dado uma formula na fnc, karp forma um grafo que tem um vértice para cada par(v,c), onde v é uma variável ou a sua negação e c é a clausula da formula que contem v. Vértices são conectados por uma aresta se eles representam associação compatível para diferente clausulas: isto é, existe uma aresta entre (v, c) para (u, d) se  ''c''&nbsp;≠&nbsp;''d''  e u e v não são suas respectivas negações. Se k denota o número de clausulas na formula fnc, então k-vertices cliques nesse grafo representam maneiras de associar valores verdade para algumas de suas variáveis a fim de satisfazer sua formula; Portanto, a formula é satisfazível se e somente se existe um clique de k vértices.

Alguns problemas NP-completo(como o do caixeiro viajante em grafos planares) podem ser resolvidos em tempo que é exponencial em uma função sublinear do tamanho do parâmetro n. Porém, como {{harvtxt|Impagliazzo|Paturi|Zane|2001}} descreve, é improvável que tais limites existam para o problema do clique em grafos arbitrários, pois isso implicaria em limites subexponenciais similares para muitos outros problemas NP-Completos.

==Referencias==
{{refbegin|colwidth=40em}}
*{{citation |último1 =Abello |primeiro1 =J. |último2 =Pardalos |primeiro2 =P. M. |último3 =Resende |primeiro3 =M. G. C. |publicação=On maximum clique problems in very large graphs |título=External Memory Algorithms |editor-nome1 =J. |editor-sobrenome1 =Abello |editor-nome2 =J. |editor-sobrenome2 =Vitter |editor2-link=Jeffrey Vitter |series=DIMACS Series on Discrete Mathematics and Theoretical Computer Science |volume=50 |páginas=119–130 |ano=1999 |publicado=[[American Mathematical Society]] |url=http://www2.research.att.com/~mgcr/abstracts/vlclq.html |isbn=0821811843}}.
*{{citation |primeiro1 =N. |último1 =Alon |autorlink1 =Noga Alon |primeiro2 =R. |último2 =Boppana |título=The monotone circuit complexity of boolean functions |periódico=[[Combinatorica]] |volume=7 |número=1 |ano=1987 |páginas=1–22 |doi=10.1007/BF02579196}}.
*{{citation |primeiro1 =N. |último1 =Alon |autorlink1 =Noga Alon |primeiro2 =M. |último2 =Krivelevich |primeiro3 =B. |último3 =Sudakov |título=Finding a large hidden clique in a random graph |periódico=Random Structures & Algorithms |volume=13 |número=3–4 |ano=1998 |páginas=457–466 |doi=10.1002/(SICI)1098-2418(199810/12)13:3/4<457::AID-RSA14>3.0.CO;2-W}}.
*{{citation |último1 = Alon |primeiro1 = N. |autorlink1 = Noga Alon |último2 = Yuster |primeiro2 = R. |último3 = Zwick |primeiro3 = U. |publicação= Finding and counting given length cycles |páginas= 354–364 |título= Proceedings of the 2nd [[European Symposium on Algorithms]], Utrecht, The Netherlands |ano= 1994}}.
*{{citation |primeiro1=K. |último1=Amano |primeiro2=A. |último2=Maruoka |publicação=A superpolynomial lower bound for a circuit computing the clique function with at most (1/6)log&nbsp;log&nbsp;''n'' negation gates |título=Proc. Symp. Mathematical Foundations of Computer Science |series=Lecture Notes in Computer Science |ano=1998 |publicado=[[Springer-Verlag]] |volume=1450 |páginas=399–408 |url=http://www.springerlink.com/content/m64ju7clmqhqmv9g/ }}{{Ligação inativa|data=maio de 2019 }}.
*{{citation |título=Proof verification and the hardness of approximation problems |primeiro1 =Sanjeev |último1 =Arora |autorlink1 =Sanjeev Arora |primeiro2 =Carsten |último2 =Lund |autorlink2 =Carsten Lund |primeiro3 =Rajeev |último3 =Motwani |autorlink3 =Rajeev Motwani |primeiro4 =Madhu |último4 =Sudan |autorlink4 =Madhu Sudan |primeiro5 =Mario |último5 =Szegedy |autorlink5 =Mario Szegedy |periódico=[[Journal of the ACM]] |volume=45 |número=3 |ano=1998 |páginas=501–555 |doi=10.1145/278298.278306 |id={{ECCC|1998|98|008}}}}. Originally presented at the 1992 [[Symposium on Foundations of Computer Science]], {{doi|10.1109/SFCS.1992.267823}}.
*{{citation |primeiro1 =S. |último1 =Arora |autorlink1 =Sanjeev Arora |primeiro2 =S. |último2 =Safra |autorlink2 =Shmuel Safra |título=Probabilistic checking of proofs: A new characterization of NP |periódico=[[Journal of the ACM]] |volume=45 |número=1 |ano=1998 |páginas=70–122 |doi=10.1145/273865.273901}}. Originally presented at the 1992 [[Symposium on Foundations of Computer Science]], {{doi|10.1109/SFCS.1992.267824}}.
*{{citation |último1 =Balas |primeiro1 =E. |último2 =Yu |primeiro2 =C. S. |título=Finding a maximum clique in an arbitrary graph |periódico=[[SIAM Journal on Computing]] |volume=15 |número=4 |ano=1986 |páginas=1054–1068 |doi=10.1137/0215075}}.
*{{citation |último1 =Battiti |primeiro1 =R. |último2 =Protasi |primeiro2 =M. |título=Reactive local search for the maximum clique problem |periódico=[[Algorithmica]] |volume=29 |número=4 |ano=2001 |páginas=610–637 |doi=10.1007/s004530010074}}.
*{{Citation |último1 =Bollobás |primeiro1 =Béla |autorlink1 =Béla Bollobás |título=Complete subgraphs are elusive |ano=1976 |periódico=Journal of Combinatorial Theory, Series B | issn=0095-8956 | volume=21 |número=1 |páginas=1–7 | doi=10.1016/0095-8956(76)90021-6}}.
*{{citation |primeiro1 =I. M. |último1 =Bomze |primeiro2 =M. |último2 =Budinich |primeiro3 =P. M. |último3 =Pardalos |primeiro4 =M. |último4 =Pelillo |publicação=The maximum clique problem |título=Handbook of Combinatorial Optimization |volume=4 |páginas=1–74 |publicado=Kluwer Academic Publishers |ano=1999 |url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.4074&rep=rep1&type=pdf}}.
*{{citation |primeiro1 =R. |último1 =Boppana |primeiro2 =M. M. |último2 =Halldórsson |título=Approximating maximum independent sets by excluding subgraphs |periódico=BIT |volume=32 |ano=1992 |páginas=180–196 |doi=10.1007/BF01994876 |número=2}}.
*{{citation |último1 =Bron |primeiro1 =C. |último2 =Kerbosch |primeiro2 =J. |título=Algorithm 457: finding all cliques of an undirected graph |ano=1973 |periódico=[[Communications of the ACM]] | doi=10.1145/362342.362367 | volume=16 |número=9 |páginas=575–577}}.
*{{citation |último1=Carraghan |primeiro1=R. |último2=Pardalos |primeiro2=P. M. |periódico=Operations Research Letters |volume=9 |ano=1990 |páginas=375–382 |url=http://www.inf.ufpr.br/renato/download/An_Exact_Algorithm_for_the_Maximum_Clique_Problem.pdf |número=6 |doi=10.1016/0167-6377(90)90057-C |acessodata=2011-12-12 |título=Cópia arquivada |arquivourl=https://web.archive.org/web/20110717210045/http://www.inf.ufpr.br/renato/download/An_Exact_Algorithm_for_the_Maximum_Clique_Problem.pdf }}.
*{{citation |último1 =Cazals |primeiro1 =F. |último2 =Karande |primeiro2 =C. |título=A note on the problem of reporting maximal cliques | url=ftp://ftp-sop.inria.fr/geometrica/fcazals/papers/ncliques.pdf |ano=2008 |periódico=[[Theoretical Computer Science (journal)|Theoretical Computer Science]] | volume=407 |número=1 |páginas=564–568 |doi=10.1016/j.tcs.2008.05.010}}.
*{{citation |primeiro1 =Jianer |último1 =Chen |primeiro2 =Xiuzhen |último2 =Huang |primeiro3 =Iyad A. |último3 =Kanj |primeiro4 =Ge |último4 =Xia |título=Strong computational lower bounds via parameterized complexity |periódico=J. Comput. Syst. Sci. | volume=72 |ano=2006 |páginas=1346–1367 | doi=10.1016/j.jcss.2006.04.007 |número=8}}
*{{citation |primeiro1 =N. |último1 =Chiba |primeiro2 =T. |último2 =Nishizeki |título=Arboricity and subgraph listing algorithms |periódico=[[SIAM Journal on Computing]] |volume=14 |número=1 |páginas=210–223 |ano=1985 |doi=10.1137/0214017}}.
*{{citation |último1 =Childs |primeiro1 =A. M. |último2 =Farhi |primeiro2 =E. |último3 =Goldstone |primeiro3 =J. |autorlink3 =Jeffrey Goldstone |último4 =Gutmann |primeiro4 =S. |título=Finding cliques by quantum adiabatic evolution |periódico=Quantum Information and Computation |volume=2 |número=3 |páginas=181–191 |ano=2002 |arxiv=quant-ph/0012104}}.
*{{citation |último1 =Childs |primeiro1 =A. M. |último2 =Eisenberg |primeiro2 =J. M. |título=Quantum algorithms for subset finding |periódico=Quantum Information and computation |volume=5 |número=7 |páginas=593–604 |ano=2005 |arxiv=quant-ph/0311038}}.
*{{citation |último1 = Clark |primeiro1 = Brent N. |último2 = Colbourn |primeiro2 = Charles J. |autorlink2 = Charles Colbourn |autorlink3 = David S. Johnson |último3 = Johnson |primeiro3 = David S. |título= Unit disk graphs |periódico= [[Discrete Mathematics (journal)|Discrete Mathematics]] | volume = 86 |número= 1–3 |ano= 1990 |páginas= 165–177 | doi = 10.1016/0012-365X(90)90358-O}}
*{{citation |primeiro =S. A. |último =Cook |autorlink =Stephen Cook |publicação=The complexity of theorem-proving procedures |ano=1971 |título=[[Symposium on Theory of Computing|Proc. 3rd ACM Symposium on Theory of Computing]] |páginas=151–158 |url=http://4mhz.de/cook.html |doi=10.1145/800157.805047 |capítulo=The complexity of theorem-proving procedures}}.
*{{citation |primeiro1 =R. G. |último1 =Downey |autorlink2 =Michael Fellows |primeiro2 =M. R. |último2 =Fellows |título=Fixed-parameter tractability and completeness. II. On completeness for W[1] |periódico=[[Theoretical Computer Science (journal)|Theoretical Computer Science]] |volume=141 |número=1–2 |ano=1995 |páginas=109–131 |doi=10.1016/0304-3975(94)00097-3}}.
*{{citation |primeiro1 =R. G. |último1 =Downey |autorlink2 =Michael Fellows |primeiro2 =M. R. |último2 =Fellows |título=Parameterized complexity |publicado=[[Springer-Verlag]] |ano=1999 |isbn = 0-387-94883-X}}.
*{{citation |primeiro1 =F. |último1 =Eisenbrand |primeiro2 =F. |último2 =Grandoni |título=On the complexity of fixed parameter clique and dominating set |periódico=[[Theoretical Computer Science (journal)|Theoretical Computer Science]] |volume=326 |número=1–3 |páginas=57–67 |ano=2004 |doi=10.1016/j.tcs.2004.05.009}}.
*{{citation |primeiro1 =David |último1 =Eppstein |autorlink1 =David Eppstein |primeiro2 =Maarten |último2 =Löffler |primeiro3 =Darren |último3 =Strash |publicação=Listing all maximal cliques in sparse graphs in near-optimal time |editor-sobrenome1 =Cheong |editor-nome1 =Otfried |editor-nome2 =Kyung-Yong |editor-sobrenome2 =Chwa |editor-nome3 =Kunsoo |editor-sobrenome3 =Park |título=21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea |series=Lecture Notes in Computer Science |volume=6506 |páginas=403–414 |publicado=Springer-Verlag |doi=10.1007/978-3-642-17517-6_36 |arxiv=1006.5440 |ano=2010 |capítulo=Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time |isbn=978-3-642-17516-9}}.
*{{citation |primeiro1 =David |último1 =Eppstein |autorlink1 =David Eppstein |primeiro2 =Darren |último2 =Strash |publicação=Listing all maximal cliques in large sparse real-world graphs |título=10th International Symposium on Experimental Algorithms |ano=2011 |arxiv=1103.0318}}.
*{{citation |primeiro1 =Paul |último1 =Erdős |autorlink1 =Paul Erdős |primeiro2 =George |último2 =Szekeres |autorlink2 =George Szekeres |título=A combinatorial problem in geometry |periódico=Compositio Mathematica |volume=2 |ano=1935 |páginas=463–470 |url=http://www.renyi.hu/~p_erdos/1935-01.pdf}}.
*{{citation |primeiro1 =S. |último1 =Even |autorlink1 =Shimon Even |primeiro2 =A. |último2 =Pnueli |autorlink2 =Amir Pnueli |primeiro3 =A. |último3 =Lempel |autorlink3 =Abraham Lempel |título=Permutation graphs and transitive graphs |periódico=[[Journal of the ACM]] |volume=19 |número=3 |páginas=400–410 |ano=1972 |doi=10.1145/321707.321710}}.
*{{citation |primeiro =T. |último =Fahle |publicação=Simple and fast: Improving a branch-and-bound algorithm for maximum clique |título=[[European Symposium on Algorithms|Proc. 10th European Symposium on Algorithms]] |series=Lecture Notes in Computer Science |publicado=Springer-Verlag |volume=2461 |ano=2002 |páginas=47–86 |doi=10.1007/3-540-45749-6_44 |capítulo=Simple and Fast: Improving a Branch-And-Bound Algorithm for Maximum Clique |isbn=978-3-540-44180-9}}.
*{{citation |primeiro =U. |último =Feige |autorlink =Uriel Feige |título=Approximating maximum clique by removing subgraphs |periódico=SIAM Journal on Discrete Mathematics |volume=18 |número=2 |páginas=219–225 |ano=2004 |doi=10.1137/S089548010240415X}}.
*{{citation |primeiro1 =U. |último1 =Feige |autorlink1 =Uriel Feige |primeiro2 =S. |último2 =Goldwasser |autorlink2 =Shafi Goldwasser |primeiro3 =L. |último3 =Lovász |autorlink3 =László Lovász |primeiro4 =S |último4 =Safra |autorlink4 =Shmuel Safra |primeiro5 =M. |último5 =Szegedy |autorlink5 =Mario Szegedy |publicação=Approximating clique is almost NP-complete |título=[[Symposium on Foundations of Computer Science|Proc. 32nd IEEE Symp. on Foundations of Computer Science]] |páginas=2–12 |ano=1991 |doi=10.1109/SFCS.1991.185341 |capítulo=Approximating clique is almost NP-complete |isbn=0-8186-2445-0}}.
*{{citation |primeiro1 =U. |último1 =Feige |autorlink1 =Uriel Feige |primeiro2 =R. |último2 =Krauthgamer |título=Finding and certifying a large hidden clique in a semirandom graph |periódico=Random Structures and Algorithms |volume=16 |número=2 |páginas=195–208 |ano=2000 |doi=10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A}}.
*{{citation |primeiro1 =M. R. |último1 =Garey |autorlink1 =Michael R. Garey |primeiro2 =D. S. |último2 =Johnson |autorlink2 =David S. Johnson |título="Strong" NP-completeness results: motivation, examples and implications |periódico=[[Journal of the ACM]] |volume=25 |páginas=499–508 |ano=1978 |doi=10.1145/322077.322090 |número=3}}.
*{{citation |último = Gavril |primeiro = F. | doi = 10.1002/net.3230030305 |número= 3 |periódico= Networks |páginas= 261–273 |título= Algorithms for a maximum clique and a maximum independent set of a circle graph | volume = 3 |ano= 1973}}.
*{{citation |primeiro1 =M. |último1 =Goldmann |primeiro2 =J. |último2 =Håstad |autorlink2 =Johan Håstad |título=A simple lower bound for monotone clique using a communication game |periódico=Information Processing Letters |volume=41 |número=4 |ano=1992 |páginas=221–226 |doi=10.1016/0020-0190(92)90184-W}}.
*{{citation |primeiro =M. C. |último =Golumbic |autorlink =Martin Charles Golumbic |título=Algorithmic Graph Theory and Perfect Graphs |series=Computer Science and Applied Mathematics |publicado=[[Academic Press]] |ano=1980 |isbn=0444515305}}.
*{{Citation | volume = 10 |número= 3 |páginas= 119–127 |último = Gröger |primeiro = Hans Dietmar |título= On the randomized complexity of monotone graph properties |periódico= Acta Cybernetica |acessodata= 2009-10-02 |ano= 1992 | url = http://www.inf.u-szeged.hu/actacybernetica/edb/vol10n3/pdf/Groger_1992_ActaCybernetica.pdf}}
*{{citation |primeiro1 =A. |último1 =Grosso |primeiro2 =M. |último2 =Locatelli |primeiro3 =F. |último3 =Della Croce |título=Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem |periódico=Journal of Heuristics |volume=10 |número=2 |ano=2004 |páginas=135–152 |doi=10.1023/B:HEUR.0000026264.51747.7f}}.
*{{citation |primeiro1 =M. |último1 =Grötschel |primeiro2 =L. |último2 =Lovász |autorlink2 =László Lovász |primeiro3 =A. |último3 =Schrijver |título=Geometric Algorithms and Combinatorial Optimization |series=Algorithms and Combinatorics |volume=2 |publicado=[[Springer–Verlag]] |ano=1988 |publicação=9.4 Coloring Perfect Graphs |páginas=296–298 |isbn=038713624X}}.
*{{citation |primeiro =G. |último =Gutin |publicação=5.3 Independent sets and cliques |título=Handbook of graph theory |editor-nome1 =J. L. |editor-sobrenome1 =Gross |editor-nome2 =J. |editor-sobrenome2 =Yellin |publicado=CRC Press |ano=2004 |isbn=9781584880905 |páginas=389–402 |series=Discrete Mathematics & Its Applications}}.
*{{citation |título=Approximations of Weighted Independent Set and Hereditary Subset Problems |primeiro =M. M. |último =Halldórsson |periódico=[[Journal of Graph Algorithms and Applications]] |volume=4 |número=1 |páginas=1–16 |ano=2000 |url=http://jgaa.info/accepted/00/Halldorsson00.4.1.pdf}}.
*{{citation |último1 =Harary |primeiro1 =F. |autorlink1 =Frank Harary |último2 =Ross |primeiro2 =I. C. |título=A procedure for clique detection using the group matrix |periódico=Sociometry |volume=20 |ano=1957 |páginas=205–215 |doi=10.2307/2785673 |número=3 |publicado=American Sociological Association |mr=0110590 |jstor=2785673}}.
*{{citation |primeiro =J. |último =Håstad |autorlink =Johan Håstad |título=Clique is hard to approximate within n<sup>1&nbsp;−&nbsp;ε</sup> |periódico=[[Acta Mathematica]] |volume=182 |número=1 |páginas=105–142 |ano=1999 |doi=10.1007/BF02392825}}.
*{{citation |primeiro1 =R. |último1 =Impagliazzo |autorlink1 =Russell Impagliazzo |primeiro2 =R. |último2 =Paturi |primeiro3 =F. |último3 =Zane |título=Which problems have strongly exponential complexity? |periódico=[[Journal of Computer and System Sciences]] |volume=63 |número=4 |ano=2001 |páginas=512–530 |doi=10.1006/jcss.2001.1774}}.
*{{citation |primeiro1 =A. |último1 =Itai |primeiro2 =M. |último2 =Rodeh |título=Finding a minimum circuit in a graph |periódico=[[SIAM Journal on Computing]] |volume=7 |número=4 |páginas=413–423 |ano=1978 |doi=10.1137/0207033}}.
*{{citation |primeiro =M. |último =Jerrum |título=Large cliques elude the Metropolis process |periódico=Random Structures and Algorithms |volume=3 |páginas=347–359 |ano=1992 |doi=10.1002/rsa.3240030402 |número=4}}.
*{{Citation |último1 =Jian |primeiro1 =T |título=An O(2<sup>0.304''n''</sup>) Algorithm for Solving Maximum Independent Set Problem |publicado=IEEE Computer Society |ano=1986 |periódico=IEEE Transactions on Computers | issn=0018-9340 | volume=35 |número=9 |páginas=847–851 | doi=10.1109/TC.1986.1676847}}.
*{{citation |editor-nome1 =D. S. |editor-sobrenome1 =Johnson |editor1-link=David S. Johnson |editor-nome2 =M. A. |editor-sobrenome2 =Trick |título=Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11–13, 1993 |series=DIMACS Series in Discrete Mathematics and Theoretical Computer Science |volume=26 |publicado=[[American Mathematical Society]] |url=http://dimacs.rutgers.edu/Volumes/Vol26.html |ano=1996 |isbn=0821866095 |autor =<!-- this comment stops Citation bot adding incorrect info here-->}}.
*{{citation |primeiro1 =D. S. |último1 =Johnson |autorlink1 =David S. Johnson |primeiro2 =M. |último2 =Yannakakis |autorlink2 =Mihalis Yannakakis |título=On generating all maximal independent sets |periódico=Information Processing Letters |volume=27 |ano=1988 |páginas=119–123 |número=3 |doi=10.1016/0020-0190(88)90065-8}}.
*{{citation |último =Karp |primeiro =Richard M. |autorlink =Richard M. Karp |url=http://www.cs.berkeley.edu/~luca/cs172/karp.pdf |publicação= Reducibility among combinatorial problems |título=Complexity of Computer Computations |editor-nome1 =R. E. |editor-sobrenome1 =Miller |editor-nome2 =J. W. |editor-sobrenome2 =Thatcher |publicado=[[Plenum Publishing Corporation|Plenum]] |local=New York |páginas=85–103 |ano=1972}}.
*{{citation |último =Karp |primeiro =Richard M. |autorlink =Richard M. Karp |publicação=Probabilistic analysis of some combinatorial search problems |título=Algorithms and Complexity: New Directions and Recent Results |editor-nome =J. F. |editor-sobrenome =Traub |publicado=[[Academic Press]] |local=New York |ano=1976 |páginas=1–19}}.
*{{citation |primeiro1 =K. |último1 =Katayama |primeiro2 =A. |último2 =Hamamoto |primeiro3 =H. |último3 =Narihisa |título=An effective local search for the maximum clique problem |periódico=Information Processing Letters |volume=95 |número=5 |ano=2005 |páginas=503–511 |doi=10.1016/j.ipl.2005.05.010}}.
*{{citation |primeiro =S. |último =Khot |publicação=Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring |título=[[Symposium on Foundations of Computer Science|Proc. 42nd IEEE Symp. Foundations of Computer Science]] |páginas=600–609 |ano=2001 |doi=10.1109/SFCS.2001.959936 |capítulo=Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring |isbn=0-7695-1116-3}}.
*{{citation |primeiro1 =T. |último1 =Kloks |primeiro2 =D. |último2 =Kratsch |primeiro3 =H. |último3 =Müller |título=Finding and counting small induced subgraphs efficiently |periódico=Information Processing Letters |volume=74 |número=3–4 |páginas=115–121 |ano=2000 |doi=10.1016/S0020-0190(00)00047-8}}.
*{{citation |último1 =Lipton |primeiro1 =R. J. |autorlink1 =Richard J. Lipton |último2 =Tarjan |primeiro2 =R. E. |autorlink2 =Robert Tarjan |título=Applications of a planar separator theorem |periódico=[[SIAM Journal on Computing]] |volume=9 |número=3 |páginas=615–627 |ano=1980 |doi=10.1137/0209046}}.
*{{citation |último1 = Luce |primeiro1 = R. Duncan |autorlink1 = R. Duncan Luce |último2 = Perry |primeiro2 = Albert D. |título= A method of matrix analysis of group structure |periódico= Psychometrika | volume = 14 |número= 2 |ano= 1949 |páginas= 95–116 | doi = 10.1007/BF02289146 | pmid = 18152948}}.
*{{citar arXiv|último1 = Magniez |primeiro1 = Frederic |último2 = Santha |primeiro2 = Miklos |último3 = Szegedy |primeiro3 = Mario | autorlink3 = Mario Szegedy |título= Quantum Algorithms for the Triangle Problem |ano= 2003 | eprint = quant-ph/0310134}}.
*{{citation |primeiro =K. |último1 =Makino |primeiro2 =T. |último2 =Uno |publicação=New algorithms for enumerating all maximal cliques |título=Algorithm Theory: SWAT 2004 |series=Lecture Notes in Computer Science |publicado=[[Springer-Verlag]] |volume=3111 |ano=2004 |páginas=260–272 |url=http://www.springerlink.com/content/p9qbl6y1v5t3xc1w/}}.
*{{citation |último1 = Moon |primeiro1 = J. W. |autorlink2 = Leo Moser |último2 = Moser |primeiro2 = L. |título= On cliques in graphs |periódico= Israel Journal of Mathematics | volume = 3 |ano= 1965 |páginas= 23–28 | mr = 0182577 | doi = 10.1007/BF02760024}}.
*{{citation |autorlink1 =Jaroslav Nešetřil |primeiro1 =J. |último1 =Nešetřil |primeiro2 =S. |último2 =Poljak |título=On the complexity of the subgraph problem |periódico=Commentationes Mathematicae Universitatis Carolinae |volume=26 |número=2 |páginas=415–419 |ano=1985}}.
*{{citation |primeiro =P. R. J. |último =Östergård |título=A fast algorithm for the maximum clique problem |periódico=Discrete Applied Mathematics |volume=120 |número=1–3 |ano=2002 |páginas=197–207 |doi=10.1016/S0166-218X(01)00290-6}}.
*{{citation |último1 =Ouyang |primeiro1 =Q. |último2 =Kaplan |primeiro2 =P. D. |último3 =Liu |primeiro3 =S. |último4 =Libchaber |primeiro4 =A. |título=DNA solution of the maximal clique problem |periódico=[[Science (journal)|Science]] |volume=278 |número=5337 |páginas=446–449 |pmid=9334300 |doi=10.1126/science.278.5337.446 |ano=1997}}.
*{{citation |último1 =Pardalos |primeiro1 =P. M. |último2 =Rogers |primeiro2 =G. P. |título=A branch and bound algorithm for the maximum clique problem |periódico=Computers & Operations Research |ano=1992 |volume=19 |número=5 |páginas=363–375 |doi=10.1016/0305-0548(92)90067-F}}.
*{{citation |primeiro =A. A. |último =Razborov |autorlink =Alexander Razborov |título=Lower bounds for the monotone complexity of some Boolean functions |língua=ru |periódico=[[Proceedings of the USSR Academy of Sciences]] |volume=281 |ano=1985 |páginas=798–801 |postscript=. English translation in ''Sov. Math. Dokl.'' '''31''' (1985): 354–357}}.
*{{citation |primeiro =J.-C. |último =Régin |publicação=Using constraint programming to solve the maximum clique problem |título=Proc. 9th Int. Conf. Principles and Practice of Constraint Programming – CP 2003 |ano=2003 |url=http://www.springerlink.com/content/8p1980dfmrt3agyp/ |series=Lecture Notes in Computer Science |publicado=[[Springer-Verlag]] |volume=2833 |páginas=634–648}}.
*{{citation |primeiro =J. M. |último =Robson |título=Algorithms for maximum independent sets |periódico=Journal of Algorithms |volume=7 |ano=1986 |páginas=425–440 |número=3 |doi=10.1016/0196-6774(86)90032-5}}.
*{{Citation |último1 =Robson |primeiro1 =J. M. |título=Finding a maximum independent set in time O(2<sup>''n''/4</sup>) |ano=2001 |url=http://www.labri.fr/perso/robson/mis/techrep.html}}.
*{{citation |último1=Rosgen |primeiro1=B |último2=Stewart |primeiro2=L |ano=2007 |periódico=Discrete Mathematics and Theoretical Computer Science |volume=9 |número=1 |páginas=127–136 |url=http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/707/1817 |acessodata=2011-12-12 |título=Cópia arquivada |arquivourl=https://web.archive.org/web/20150923215449/http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/707/1817 }}.
*{{citation |primeiro =M. |último =Sipser |autorlink =Michael Sipser |título=[[Introduction to the Theory of Computation]] |publicado=[[The Thomson Corporation|International Thompson Publishing]] |ano=1996 |isbn=053494728X}}.
*{{citation |primeiro1=R. E. |último1=Tarjan |autorlink1=Robert Tarjan |primeiro2=A. E. |último2=Trojanowski |título=Finding a maximum independent set |periódico=[[SIAM Journal on Computing]] |volume=6 |ano=1977 |páginas=537–546 |url=ftp://db.stanford.edu/pub/cstr.old/reports/cs/tr/76/550/CS-TR-76-550.pdf |doi=10.1137/0206038 |número=3 }}{{Ligação inativa|data=maio de 2019 }}.
*{{citation |primeiro1 =E. |último1 =Tomita |primeiro2 =T. |último2 =Kameda |título=An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments |periódico=Journal of Global Optimization |volume=37 |número=1 |ano=2007 |páginas=95–111 |doi=10.1007/s10898-006-9039-7}}.
*{{citation |primeiro1 =E. |último1 =Tomita |primeiro2 =T. |último2 =Seki |publicação=An efficient branch-and-bound algorithm for finding a maximum clique |título=Discrete Mathematics and Theoretical Computer Science |series=Lecture Notes in Computer Science |publicado=Springer-Verlag |volume=2731 |ano=2003 |páginas=278–289 |doi=10.1007/3-540-45066-1_22 |capítulo=An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique |isbn=978-3-540-40505-4}}.
*{{citation |primeiro1 =E. |último1 =Tomita |primeiro2 =A. |último2 =Tanaka |primeiro3 =H. |último3 =Takahashi |título=The worst-case time complexity for generating all maximal cliques and computational experiments |periódico=[[Theoretical Computer Science (journal)|Theoretical Computer Science]] |volume=363 |número=1 |páginas=28–42 |ano=2006 |doi=10.1016/j.tcs.2006.06.015}}.
*{{citation |primeiro1 =S. |último1 =Tsukiyama |primeiro2 =M. |último2 =Ide |primeiro3 =I. |último3 =Ariyoshi |primeiro4 =I. |último4 =Shirakawa |título=A new algorithm for generating all the maximal independent sets |periódico=[[SIAM Journal on Computing]] |volume=6 |ano=1977 |páginas=505–517 |doi=10.1137/0206036 |número=3}}.
*{{citation |último =Valiant |primeiro =L. G. |publicação=Exponential lower bounds for restricted monotone circuits |título=[[Symposium on Theory of Computing|Proc. 15th ACM Symposium on Theory of Computing]] |ano=1983 |páginas=110–117 |doi=10.1145/800061.808739 |capítulo=Exponential lower bounds for restricted monotone circuits |isbn=0897910990}}.
*{{citation |primeiro1 =V. |último1 =Vassilevska |primeiro2 =R. |último2 =Williams |autorlink2 =Ryan Williams (computer scientist) |publicação=Finding, minimizing and counting weighted subgraphs |título=[[Symposium on Theory of Computing|Proc. 41st ACM Symposium on Theory of Computing]] |ano=2009 |páginas=455–464 |doi=10.1145/1536414.1536477 |capítulo=Finding, minimizing, and counting weighted subgraphs |isbn=9781605585062}}.
*{{citation |último =Wegener |primeiro =I. |título=On the complexity of branching programs and decision trees for clique functions |periódico=[[Journal of the ACM]] |volume=35 |número=2 |páginas=461–472 |ano=1988 |doi=10.1145/42282.46161}}.
*{{citation |primeiro =R. |último =Yuster |título=Finding and counting cliques and independent sets in ''r''-uniform hypergraphs |periódico=Information Processing Letters |volume=99 |número=4 |páginas=130–134 |ano=2006 |doi=10.1016/j.ipl.2006.04.005}}.
*{{citation |primeiro =D. |último =Zuckerman |publicação=Linear degree extractors and the inapproximability of max clique and chromatic number |título=[[Symposium on Theory of Computing|Proc. 38th ACM Symp. Theory of Computing]] |páginas=681–690 |ano=2006 |doi=10.1145/1132516.1132612 |id={{ECCC|2005|05|100}}|capítulo=Linear degree extractors and the inapproximability of max clique and chromatic number |isbn=1595931341}}.
{{refend}}

[[Categoria:Erros de computador]]
[[Categoria:Problemas NP-completos]]

[[fr:Clique (théorie des graphes)#Problème de la clique]]