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
    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
    0 references
    0 references
    0 references