PARALLEL ALGORITHMS FOR MAXIMAL CLIQUES IN CIRCLE GRAPHS AND UNRESTRICTED DEPTH SEARCH

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.

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

CNPq[55.0895/07-8]

CNPq[30.5362/06-2]

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

CNPq[30.1652/09-0]

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

CNPq[62.0171/06-5]

FUNDECT

FUNDECT[41/100.115/2006]

FAPERJ

FAPERJ