PARALLEL ALGORITHMS FOR MAXIMAL CLIQUESIN CIRCLE GRAPHS AND UNRESTRICTED DEPTHSEARCH

We present parallel algorithms on the BSP/CGM model,with p processors, to count and generate all the maximal cliques of acircle graph with n vertices and m edges. To count the number of allthe maximal cliques, without actually generating them, our algorithmrequires O(log p) communication rounds with O(nm/p) local computationtime. We also present an algorithm to generate the first maximalclique in O(log p) communication rounds with O(nm/p) local computation,and to generate each one of the subsequent maximal cliquesthis algorithm requires O(log p) communication rounds with O(m/p)local computation. The maximal cliques generation algorithm is basedon generating all maximal paths in a directed acyclic graph, and wepresent an algorithm for this problem that uses O(log p) communicationrounds with O(m/p) local computation for each maximal path.We also show that the presented algorithms can be extended to theCREW PRAM model