Cliques Maximais em Grafos Círculo - Cárceres, Edson Norberto; Szwarcfiter, Jayme Luiz (Anais do International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD); 1993: Anais do V Simpósio Brasileiro de Arquitetura de Computadores e Processamento de Alto Desempenho, 1993)
Apresentamos uma implementação em uma CREW PRAM de um algoritmo paralelo para geração de todas as cliques maximais em um grafo círculo. O algoritmo é executado em tempo paralelo O(α log 2 n) com n 3 processadores, onde n,m e α são o número de vértices, arestas e cliques maximais do grafo, respectivamente. Vamos também apresentar um algoritmo paralelo para computar o número de cliques maximais α k de tamanho k, o número total de cliques maximais α e a clique máxima de um grafo círculo em tempo paralelo O(log 2  n) com n 3 , nM(n) e n 3 processadores, respectivamente, em uma CREW PRAM, onde M(n) é o número de processadores necessários para efetuar uma multiplicação de duas matrizes n x n.