Parallel algorithms for maximal cliques in circle graphs and unrestricted depth search
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 3, pp. 293-311.

We present parallel algorithms on the BSP/CGM model, with p processors, to count and generate all the maximal cliques of a circle graph with n vertices and m edges. To count the number of all the maximal cliques, without actually generating them, our algorithm requires O(log p) communication rounds with O(nm/p) local computation time. We also present an algorithm to generate the first maximal clique in O(log p) communication rounds with O(nm/p) local computation, and to generate each one of the subsequent maximal cliques this algorithm requires O(log p) communication rounds with O(m/p) local computation. The maximal cliques generation algorithm is based on generating all maximal paths in a directed acyclic graph, and we present an algorithm for this problem that uses O log (p) communication rounds with O(m/p) local computation for each maximal path. We also show that the presented algorithms can be extended to the CREW PRAM model.

DOI : 10.1051/ita/2010016
Classification : 68W10, 05C85, 05C69
Mots-clés : BSP/CGM algorithm, PRAM algorithm, circle graph, maximal clique, unrestricted depth search 
@article{ITA_2010__44_3_293_0,
     author = {C\'aceres, E. N. and Song, S. W. and Szwarcfiter, J. L.},
     title = {Parallel algorithms for maximal cliques in circle graphs and unrestricted depth search},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {293--311},
     publisher = {EDP-Sciences},
     volume = {44},
     number = {3},
     year = {2010},
     doi = {10.1051/ita/2010016},
     mrnumber = {2761521},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita/2010016/}
}
TY  - JOUR
AU  - Cáceres, E. N.
AU  - Song, S. W.
AU  - Szwarcfiter, J. L.
TI  - Parallel algorithms for maximal cliques in circle graphs and unrestricted depth search
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2010
SP  - 293
EP  - 311
VL  - 44
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita/2010016/
DO  - 10.1051/ita/2010016
LA  - en
ID  - ITA_2010__44_3_293_0
ER  - 
%0 Journal Article
%A Cáceres, E. N.
%A Song, S. W.
%A Szwarcfiter, J. L.
%T Parallel algorithms for maximal cliques in circle graphs and unrestricted depth search
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2010
%P 293-311
%V 44
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita/2010016/
%R 10.1051/ita/2010016
%G en
%F ITA_2010__44_3_293_0
Cáceres, E. N.; Song, S. W.; Szwarcfiter, J. L. Parallel algorithms for maximal cliques in circle graphs and unrestricted depth search. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 3, pp. 293-311. doi : 10.1051/ita/2010016. http://archive.numdam.org/articles/10.1051/ita/2010016/

[1] C.E.R. Alves, E.N. Cáceres, A.A. Castro Jr, S.W. Song and J.L. Szwarcfiter, Efficient Parallel Implementation of Transitive Closure of Digraphs, in 10th European PVM/MPI Users' Group Conference. Edited by J. Dongarra, D. Laforenza and S. Orlando, Springer Verlag, Berlin (2003) 126-133.

[2] R. Anderson and E. Mayr, Parallelism and Greedy Algorithms. Technical Report STAN-CS-84-1003, Computer Science Department, Stanford University Bonn (1984).

[3] A. Bouchet, Reducing Prime Graphs and Recognizing Circle Graphs. Combinatorica 7 (1987) 243-254. | Zbl

[4] E.N. Cáceres, S.W. Song and J.L. Szwarcfiter, A Coarse-Grained Parallel Algorithm for Maximal Cliques in Circle Graphs, in Proc. The 2001 International Conference on Computational Science. Springer Verlag, Berlin (2001) 638-647. | Zbl

[5] E.N. Cáceres, S.W. Song and J.L. Szwarcfiter, A Parallel Unrestricted Depth Search Algorithm, in Proc. 2001 International Conference on Parallel and Distributed Processing Techniques and Applications (2001) 521-526.

[6] E.N. Cáceres, S.W. Song and J.L. Szwarcfiter, A Parallel Algorithm for Transitive Closure, in Proc. 14th IASTED International Conference on Parallel and Distributed Computing and Systems. IASTED, Zurich (2002) 116-118.

[7] A. Chan and F. Dehne, A Note on Coarse Grained Parallel Integer Sorting. Parallel Process. Lett. 9 (1999) 533-538.

[8] N. Chiba and T. Nishizeki, Arboricity and subgraphs listing algorithms. SIAM J. Comput. 14 (1985) 210-223. | Zbl

[9] E. Dahlhaus and M. Karpinski, A Fast Parallel Algorithm for Computing all Maximal Cliques in a Graph and the Related Problems, in Proc. Scandinavian Workshop on Algorithm Theory - SWAT (1988) 139-144. | Zbl

[10] F. Dehne (Ed.), Coarse grained parallel algorithms. Algorithmica 24 (1999) 173-426. | Zbl

[11] F. Dehne, A. Ferreira, E. Cáceres, S.W. Song and A. Roncato, Efficient Parallel Graph Algorithms For Coarse Grained Multicomputers and BSP. Algorithmica 33 (2002) 183-200. | Zbl

[12] A. Ferreira and N. Schabanel, A randomized BSP/CGM algorithm for the maximal independent set. Parallel Process. Lett. 9 (2000) 411-422.

[13] C.P. Gabor, W.L. Hsu and K.J. Supowit, Recognizing Circle Graphs in Polynomial Time. J. Assoc. Comput. Mach. 36 (1989) 435-474. | Zbl

[14] R.K. Ghosh and G.P. Bhattacharjee, A Parallel Search Algorithm for Directed Acyclic Graphs. BIT 24 (1984) 134-150. | Zbl

[15] E. Gioan, C. Paul, M. Tedder and D. Corneil, Quasi-linear circle graph recognition. Technical Report, University of Toronto (2009).

[16] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press (1980). | Zbl

[17] R. Gupta, J. Walrand and O. Goldschmidt, Maximal Cliques in Unit Disk Graphs: Polynomial Approximation, in Proc. International Network Optimization Conference (INOC), Lisbon (2005).

[18] C.W. Ho and R.C.T. Lee, Efficient Parallel Algorithms for Finding Maximal Cliques, Clique Trees, and Minimum Coloring on Chordal Graphs. Inf. Process. Lett. 28 (1988) 301-309. | Zbl

[19] E. Jennings and L. Motyckova, A Distributed Algorithm for finding All Maximal Cliques in a Network Graph, in Proc. of the 1st Latin American Symposium on Theoretical Informatics (LATIN'92) (1992) 281-293.

[20] R.M. Karp and V. Ramachandran, Parallel Algorithms for Shared-Memory Machines. Edited by J. van Leeuwen Handbook of Theoretical Computer Science. MIT Press/Elsevier (1990) 869-941. | Zbl

[21] P.N. Klein, Efficient Parallel Algorithms for Chordal Graphs. SIAM J. Comput. 25 (1996) 797-827. | Zbl

[22] K. Makino and T. Uno, New Algorithms for Enumerating All Maximal Cliques, in Proc. Scandinavian Workshop on Algorithm Theory - SWAT (2004) 260-272. | Zbl

[23] J.W. Moon and L. Moser, On cliques in graphs. Israel J. Math 3 (1965) 23-28. | Zbl

[24] W. Naji, Graphes des Cordes, Caractérisation et Reconnaissance. Disc. Math. 54 (1985) 329-337. | Zbl

[25] J. Naor, M. Naor and A.A. Schäffer, Fast Parallel Algorithms for Chordal Graphs. SIAM J. Comput. 18 (1989) 327-349. | Zbl

[26] F. Protti, F.M.G. França and J.L. Szwarcfiter, On Computing All Maximal Cliques Distributedly, in Proc. Workshop on Parallel Algorithms for Irregularly Structured Problems (IRREGULAR) (1997) 37-48.

[27] J.P. Spinrad, Recognition of Circle Graphs. J. Algor. 16 (1994) 264-282. | Zbl

[28] J.L. Szwarcfiter and M. Barroso, Enumerating the Maximal Cliques of Circle Graph, Graph Theory, Combinatorics, Algorithms and Applications. edited by F.R.K. Chung, R.L. Graham and D.F. Hsu, SIAM Publications (1991) 511-517. | Zbl

[29] R.E. Tarjan, Depth First Search and Linear Graph Algorithms. SIAM J. Comput. 1 (1972) 146-160. | Zbl

[30] S. Tsukiyama, M. Ide, H. Arujoshi and H. Ozaki, A New Algorithm for Generating the Maximal Independent Sets. SIAM J. Comput. 6 (1997) 505-517. | Zbl

[31] L.G. Valiant, A Bridging Model for Parallel Computation. Communication of the ACM 33 (1990) 103-111.

[32] C.S. Wang and R.S. Chang, A Parallel Maximal Cliques Algorithm for Interval Graphs with Applications. J. Inf. Sci. Eng. 13 (1997) 649-663.

[33] Y. Zhang, Parallel Algorithms for Problems Involving Directed Graphs. Ph.D. thesis, Department of Computer Science, Drexel University (1990).

[34] Y. Zhang, F.N. Abu-Khzam, N.E. Baldwin, E.J. Chesler, N.F. Samatova and M.A. Langston, Genome-Scale Computational Approaches to Memory-Intensive Applications in Systems Biology. Proceedings of SC, Seattle, Washington (2005).

Cité par Sources :