A dominating set D in a graph G=(V,E) is a set of vertices in V such that every vertex in v-d is adjacent to some vertex in D. A dominating set is connected if the graph induced by D is connected. The minimum-weight connected dominating set problem is the problem of finding a connected dominating set with the smallest total weight of vertices in D. This problem is known to be NP-hard for general graphs. Thus, by restricting the shape of graphs, some polynomial time sequential algorithms have been developed. In this paper, we propose an efficient parallel algorithm for finding a minimum-weight connected dominating set for trapezoid graphs in O(log~2n) time using O(n~3) processors on a CREW PRAM.
展开▼
