# Parallel Algorithms for Maximal Cliques in Circle Graphs and Unrestricted Depth Search

E. N. Cáceres; S. W. Song; J. L. Szwarcfiter

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 44, Issue: 3, page 293-311
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topCáceres, E. N., Song, S. W., and Szwarcfiter, J. L.. "Parallel Algorithms for Maximal Cliques in Circle Graphs and Unrestricted Depth Search." RAIRO - Theoretical Informatics and Applications 44.3 (2010): 293-311. <http://eudml.org/doc/250793>.

@article{Cáceres2010,

abstract = {
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.
},

author = {Cáceres, E. N., Song, S. W., Szwarcfiter, J. L.},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {BSP/CGM algorithm; PRAM algorithm; circle graph;
maximal clique; unrestricted depth search.; maximal clique; unrestricted depth search},

language = {eng},

month = {10},

number = {3},

pages = {293-311},

publisher = {EDP Sciences},

title = {Parallel Algorithms for Maximal Cliques in Circle Graphs and Unrestricted Depth Search},

url = {http://eudml.org/doc/250793},

volume = {44},

year = {2010},

}

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

DA - 2010/10//

PB - EDP Sciences

VL - 44

IS - 3

SP - 293

EP - 311

AB -
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.

LA - eng

KW - BSP/CGM algorithm; PRAM algorithm; circle graph;
maximal clique; unrestricted depth search.; maximal clique; unrestricted depth search

UR - http://eudml.org/doc/250793

ER -

## References

top- 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.
- R. Anderson and E. Mayr, Parallelism and Greedy Algorithms. Technical Report STAN-CS-84-1003, Computer Science Department, Stanford University Bonn (1984).
- A. Bouchet, Reducing Prime Graphs and Recognizing Circle Graphs. Combinatorica7 (1987) 243–254. Zbl0666.05037
- 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. Zbl0983.68584
- 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.
- 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.
- A. Chan and F. Dehne, A Note on Coarse Grained Parallel Integer Sorting. Parallel Process. Lett.9 (1999) 533–538.
- N. Chiba and T. Nishizeki, Arboricity and subgraphs listing algorithms. SIAM J. Comput.14 (1985) 210–223. Zbl0572.68053
- 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. Zbl0656.68070
- F. Dehne (Ed.), Coarse grained parallel algorithms. Algorithmica24 (1999) 173–426. Zbl0937.00016
- F. Dehne, A. Ferreira, E. Cáceres, S.W. Song and A. Roncato, Efficient Parallel Graph Algorithms For Coarse Grained Multicomputers and BSP. Algorithmica33 (2002) 183–200. Zbl0994.68177
- A. Ferreira and N. Schabanel, A randomized BSP/CGM algorithm for the maximal independent set. Parallel Process. Lett.9 (2000) 411–422.
- C.P. Gabor, W.L. Hsu and K.J. Supowit, Recognizing Circle Graphs in Polynomial Time. J. Assoc. Comput. Mach.36 (1989) 435–474. Zbl0825.68417
- R.K. Ghosh and G.P. Bhattacharjee, A Parallel Search Algorithm for Directed Acyclic Graphs. BIT24 (1984) 134–150. Zbl0542.68049
- E. Gioan, C. Paul, M. Tedder and D. Corneil, Quasi-linear circle graph recognition. Technical Report, University of Toronto (2009). Zbl1303.05190
- M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs. Academic Press (1980). Zbl0541.05054
- R. Gupta, J. Walrand and O. Goldschmidt, Maximal Cliques in Unit Disk Graphs: Polynomial Approximation, in Proc. International Network Optimization Conference (INOC), Lisbon (2005).
- 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. Zbl0658.68079
- 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.
- 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. Zbl0900.68267
- P.N. Klein, Efficient Parallel Algorithms for Chordal Graphs. SIAM J. Comput.25 (1996) 797–827. Zbl0857.68049
- K. Makino and T. Uno, New Algorithms for Enumerating All Maximal Cliques, in Proc. Scandinavian Workshop on Algorithm Theory – SWAT (2004) 260–272. Zbl1095.68626
- J.W. Moon and L. Moser, On cliques in graphs. Israel J. Math3 (1965) 23–28. Zbl0144.23205
- W. Naji, Graphes des Cordes, Caractérisation et Reconnaissance. Disc. Math.54 (1985) 329–337. Zbl0567.05033
- J. Naor, M. Naor and A.A. Schäffer, Fast Parallel Algorithms for Chordal Graphs. SIAM J. Comput.18 (1989) 327–349. Zbl0672.05055
- 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.
- J.P. Spinrad, Recognition of Circle Graphs. J. Algor.16 (1994) 264–282. Zbl0797.68130
- 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. Zbl0752.05033
- R.E. Tarjan, Depth First Search and Linear Graph Algorithms. SIAM J. Comput.1 (1972) 146–160. Zbl0251.05107
- 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.
- L.G. Valiant, A Bridging Model for Parallel Computation. Communication of the ACM33 (1990) 103–111.
- 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.
- Y. Zhang, Parallel Algorithms for Problems Involving Directed Graphs. Ph.D. thesis, Department of Computer Science, Drexel University (1990).
- 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).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.