Research Article

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

Cáceres, E. N.^a1, Song, S. W.^a2 and Szwarcfiter, J. L.^a3

^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