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

\textit{J. Naor}, \textit{M. Naor} and \textit{A. A. Schaffer} [Proc. 19th Ann. ACM Symp. Theory Comput., 355-364 (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^ 2 n)\) time with \(O(n^{5+\epsilon})\) processors and, using this result, they solved all the other problems. We propose another parallel algorithm for maximal cliques which can be executed in \(O(\log^ 2 n)\) time by using only \(O(n^ 3)\) processors. This result reduces the processor bound from \(O(n^{5+\epsilon})\) to \(O(n^ 3)\) 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.