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.
Keywords: 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://www.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://www.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://www.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, Volume 44 (2010) no. 3, pp. 293-311. doi : 10.1051/ita/2010016. http://www.numdam.org/articles/10.1051/ita/2010016/
[1] 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.
, , , and ,[2] Parallelism and Greedy Algorithms. Technical Report STAN-CS-84-1003, Computer Science Department, Stanford University Bonn (1984).
and ,[3] Reducing Prime Graphs and Recognizing Circle Graphs. Combinatorica 7 (1987) 243-254. | Zbl
,[4] 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
, and ,[5] A Parallel Unrestricted Depth Search Algorithm, in Proc. 2001 International Conference on Parallel and Distributed Processing Techniques and Applications (2001) 521-526.
, and ,[6] A Parallel Algorithm for Transitive Closure, in Proc. 14th IASTED International Conference on Parallel and Distributed Computing and Systems. IASTED, Zurich (2002) 116-118.
, and ,[7] A Note on Coarse Grained Parallel Integer Sorting. Parallel Process. Lett. 9 (1999) 533-538.
and ,[8] Arboricity and subgraphs listing algorithms. SIAM J. Comput. 14 (1985) 210-223. | Zbl
and ,[9] 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
and ,[10] Coarse grained parallel algorithms. Algorithmica 24 (1999) 173-426. | Zbl
(Ed.),[11] Efficient Parallel Graph Algorithms For Coarse Grained Multicomputers and BSP. Algorithmica 33 (2002) 183-200. | Zbl
, , , and ,[12] A randomized BSP/CGM algorithm for the maximal independent set. Parallel Process. Lett. 9 (2000) 411-422.
and ,[13] Recognizing Circle Graphs in Polynomial Time. J. Assoc. Comput. Mach. 36 (1989) 435-474. | Zbl
, and ,[14] A Parallel Search Algorithm for Directed Acyclic Graphs. BIT 24 (1984) 134-150. | Zbl
and ,[15] Quasi-linear circle graph recognition. Technical Report, University of Toronto (2009).
, , and ,[16] Algorithmic Graph Theory and Perfect Graphs. Academic Press (1980). | Zbl
,[17] Maximal Cliques in Unit Disk Graphs: Polynomial Approximation, in Proc. International Network Optimization Conference (INOC), Lisbon (2005).
, and ,[18] Efficient Parallel Algorithms for Finding Maximal Cliques, Clique Trees, and Minimum Coloring on Chordal Graphs. Inf. Process. Lett. 28 (1988) 301-309. | Zbl
and ,[19] 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.
and ,[20] Parallel Algorithms for Shared-Memory Machines. Edited by J. van Leeuwen Handbook of Theoretical Computer Science. MIT Press/Elsevier (1990) 869-941. | Zbl
and ,[21] Efficient Parallel Algorithms for Chordal Graphs. SIAM J. Comput. 25 (1996) 797-827. | Zbl
,[22] New Algorithms for Enumerating All Maximal Cliques, in Proc. Scandinavian Workshop on Algorithm Theory - SWAT (2004) 260-272. | Zbl
and ,[23] On cliques in graphs. Israel J. Math 3 (1965) 23-28. | Zbl
and ,[24] Graphes des Cordes, Caractérisation et Reconnaissance. Disc. Math. 54 (1985) 329-337. | Zbl
,[25] Fast Parallel Algorithms for Chordal Graphs. SIAM J. Comput. 18 (1989) 327-349. | Zbl
, and ,[26] On Computing All Maximal Cliques Distributedly, in Proc. Workshop on Parallel Algorithms for Irregularly Structured Problems (IRREGULAR) (1997) 37-48.
, and ,[27] Recognition of Circle Graphs. J. Algor. 16 (1994) 264-282. | Zbl
,[28] 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
and ,[29] Depth First Search and Linear Graph Algorithms. SIAM J. Comput. 1 (1972) 146-160. | Zbl
,[30] A New Algorithm for Generating the Maximal Independent Sets. SIAM J. Comput. 6 (1997) 505-517. | Zbl
, , and ,[31] A Bridging Model for Parallel Computation. Communication of the ACM 33 (1990) 103-111.
,[32] A Parallel Maximal Cliques Algorithm for Interval Graphs with Applications. J. Inf. Sci. Eng. 13 (1997) 649-663.
and ,[33] Parallel Algorithms for Problems Involving Directed Graphs. Ph.D. thesis, Department of Computer Science, Drexel University (1990).
,[34] Genome-Scale Computational Approaches to Memory-Intensive Applications in Systems Biology. Proceedings of SC, Seattle, Washington (2005).
, , , , and ,Cited by Sources: