Cliques Maximais em Grafos Círculo
Abstract
We describe a implementation in a CREW PRAM of a parallel algorithm for generating all maximal cliques in a circle graph G. The algorithm requires O(α log2 n) parallel time with n3 processors, where m, n and α are the number of vertices, edges and maximal cliques of G. In addition, we show that the number of such cliques, the number of cliques of length k and a maximum clique can be computed in O(log2 n) parallel time with n3, nM(n) and n3, respectively, in a CREW PRAM where M(n) is the number of processors required to multiply two n x n matrices.
References
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.
Published
1993-09-07
How to Cite
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.
