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

Abstract

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

How to cite

top

Cá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
  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. Combinatorica7 (1987) 243–254.  
  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.  
  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.  
  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.  
  10. F. Dehne (Ed.), Coarse grained parallel algorithms. Algorithmica24 (1999) 173–426.  
  11. 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.  
  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.  
  14. R.K. Ghosh and G.P. Bhattacharjee, A Parallel Search Algorithm for Directed Acyclic Graphs. BIT24 (1984) 134–150.  
  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).  
  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.  
  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.  
  21. P.N. Klein, Efficient Parallel Algorithms for Chordal Graphs. SIAM J. Comput.25 (1996) 797–827.  
  22. K. Makino and T. Uno, New Algorithms for Enumerating All Maximal Cliques, in Proc. Scandinavian Workshop on Algorithm Theory – SWAT (2004) 260–272.  
  23. J.W. Moon and L. Moser, On cliques in graphs. Israel J. Math3 (1965) 23–28.  
  24. W. Naji, Graphes des Cordes, Caractérisation et Reconnaissance. Disc. Math.54 (1985) 329–337.  
  25. J. Naor, M. Naor and A.A. Schäffer, Fast Parallel Algorithms for Chordal Graphs. SIAM J. Comput.18 (1989) 327–349.  
  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.  
  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.  
  29. R.E. Tarjan, Depth First Search and Linear Graph Algorithms. SIAM J. Comput.1 (1972) 146–160.  
  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.  
  31. L.G. Valiant, A Bridging Model for Parallel Computation. Communication of the ACM33 (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).  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.