Parallel algorithms for the domination problems in trapezoid graphs (Q1356505)

The problem of finding the minimum weight dominating set (MWDS) in an arbitrary graph is known to be an NP-complete problem. For the class of trapezoid graphs, polynomial algorithms solving this problem are known. In the present paper some parallel algorithms for solving MWDS and related problems are introduced. All these algorithms take \(O(\log^2n)\) time on EREW PRAM with \(O(\max\{n^3/\log^2n, n^{2.376}\})\) processors for MWDS required. The number of processors for other domination problems is \(O(\max\{nm^2/\log^2n, m^{2.376}\})\), where \(n\) is the number of vertices and \(m\) the number of edges in the trapezoid graph. The basic idea of algorithms is a reduction of a trapezoid graph to an auxiliary digraph and finding a shortest or minimum weight path in this digraph.