Abstract | ||
---|---|---|
In this paper, we show that the problem of finding a minimum weight dominating set in a permutation graph, where a positive weight is assigned to each vertex, is in NC by presenting an O (log n ) parallel algorithm with polynomially many processors on the CRCW model. |
Year | DOI | Venue |
---|---|---|
1995 | 10.1006/jpdc.1995.1093 | J. Parallel Distrib. Comput. |
Keywords | Field | DocType |
minimum weight,permutation graph,parallel algorithm,dominating set | Permutation graph,Graph theory,Discrete mathematics,Dominating set,Combinatorics,Vertex (geometry),Parallel algorithm,Permutation,Minimum weight,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
28 | 2 | Journal of Parallel and Distributed Computing |
Citations | PageRank | References |
5 | 6.78 | 4 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Chong Jye Rhee | 1 | 31 | 11.62 |
Dhall | 2 | 271 | 80.48 |
S. Lakshmivarahan | 3 | 412 | 66.03 |