Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs

Naor et al. (1987) proposed parallel algorithms for several problems on chordal graphs such as computing maximal cliques, a minimum coloring, a perfect elimination scheme and so on. They first solved the problem of computing maximal cliques in O(log²n) time with O(n^5+ε{lunate}) processors and, using this result, they solved all the other problems. In this paper we propose another parallel algorithm for maximal cliques which can be executed in O(log²n) time by using only O(n³) processors. This results reduces the processor bound from O(n^5+ε{lunate}) to O(n³) for all the problems solved by Naor et al. Based upon this result we propose another two algorithms for computing a clique tree and minimum coloring which are more efficient than those proposed by Naor et al.