RAIRO - Theoretical Informatics and Applications

Research Article

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

E. N. Cáceresa1, S. W. Songa2 and J. L. Szwarcfitera3

a1 Universidade Federal de Mato Grosso do Sul, Faculdade de Computação, 79070-900 Campo Grande, MS, Brazil; edson@facom.ufms.br

a2 Universidade de São Paulo, Instituto de Matemática e Estatística, 05508-900 São Paulo, SP, Brazil; visiting professor of Universidade Federal do ABC; song@ime.usp.br

a3 Universidade Federal do Rio de Janeiro, Instituto de Matemática, Núcleo de Computação Eletrônica and COPPE, 21.945-970 Rio de Janeiro, RJ, Brazil; jayme@nce.ufrj.br

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.

(Received March 30 2009)

(Accepted June 2 2010)

(Online publication June 23 2010)

Key Words:

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

Mathematics Subject Classification:

  • 68W10;
  • 05C85;
  • 05C69
Metrics