Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs (Q1111390)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs |
scientific article |
Statements
Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs (English)
0 references
1988
0 references
\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.
0 references
graph separator
0 references
parallel algorithms
0 references
chordal graphs
0 references
maximal cliques
0 references
minimum coloring
0 references
clique tree
0 references