Parallel algorithms for the domination problems in trapezoid graphs (Q1356505)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Parallel algorithms for the domination problems in trapezoid graphs |
scientific article |
Statements
Parallel algorithms for the domination problems in trapezoid graphs (English)
0 references
25 November 1997
0 references
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.
0 references
minimum weight dominating set
0 references
NP-complete
0 references
trapezoid graphs
0 references
polynomial algorithms
0 references
parallel algorithms
0 references