The parallel solution of domination problems on chordal and strongly chordal graphs (Q1331893)

This paper discusses the problem of the existence of a dominating clique in a chordal graph. The equivalence of the dominating set problem and the minimum dominating clique problem for strongly chordal graphs has also been proved. Further, it has been proved that both problems are equivalent to the cover problem viz. the problem of finding a minimum subset of the hyperedge set that covers all vertices of a given \(\beta\)- acyclic hypergraph (the class of \(\beta\)-acyclic hypergraphs corresponds to the class of maximal clique sets of strongly chordal graphs). Finally, an efficient parallel algorithm for the cover problem for \(\alpha\)- acyclic hypergraphs which includes also an efficient parallel algorithm for the domination problems has been presented.