Cliques Maximais em Grafos Círculo
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(log2 n) 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.
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
Como Citar
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.
