Cliques Maximais em Grafos Círculo

  • Edson Norberto Cárceres UFMS
  • Jayme Luiz Szwarcfiter UFRJ

Resumo


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(α log2 n) com n3 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(logn) com n3, nM(n) e n3 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.

Referências

A. Bouchet. Reducing prime graphs and recognizing circle graphs. Combinatorica, 7:243-254, 1987.

E.N. Cáceres. Algoritmo paralelo para busca irrestrita. XIX SEMISH - SBC, 1-15, 1992.

E.N. Cáceres. Algoritmos Paralelos para Problemas em Grafos. PhD thesis, COPPE - UFRJ, Rio de Janeiro - RJ, 1992.

D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. J. Symbolic Computation, 9:251-280, 1990.

W.H. Cunningham. Decomposition of directed graphs. SJAM J. Alg. and Disc. Methods, 3:214-228, 1982.

W.H. Cunningham and J. Edmonds. A combinatorial decomposition theory. Canad. J. Math., 32:734-765, 1980.

E. Dahlhaus and M. Karpinski. A Fast parallel algorithm for computing all maximal cliques in a graph and the related problems. Technical Report 8516-CS, Institut fur Informatik der Universitat Bonn, Bonn, 1987.

C.P. Gabor, W.L. Hsu, and K.J. Supowit. Recognizing circle graphs in polynomial time. J. of Assoc. Comput. Mach., 36:435-474, 1989.

R.M. Karp and V. Ramachandran. Parallel algorithms for shared-memory machines. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science-Vol. A, chapter 17, pages 869-941, The MIT Press/Elsevier, 1990.

J.W. Moon and L. Moser. On cliques in graphs. Israel J. Math., 3:23-28, 1965.

W. Naji. Graphes des cordes, caractérisation et reconnaissance. Disc. Math., 54:329-337, 1985.

M.B. Novick. Parallel algorithms for intersection graphs. PhD thesis, Department of Computer Science, Cornell University, Ithaca, NY, 1990.
Publicado
07/09/1993
CÁRCERES, Edson Norberto; SZWARCFITER, Jayme Luiz. Cliques Maximais em Grafos Círculo. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 5. , 1993, Florianópolis/SC. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 1993 . p. 398-411. DOI: https://doi.org/10.5753/sbac-pad.1993.23047.