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