Generalized Weakly Connected Domination in Unit Disk Graphs

摘要

A weakly connected dominating set W of a graph G is a dominating set, such that the subgraph consisting of V (G) and all edges incident on vertices in W is connected. Recently, several authors generalize it to [r,R]-dominating set which means a distance r-dominating set that can be connected by adding paths with length within R. In this paper, we restrict [r,R]-dominating set in unit disk graphs for practical reasons,and present an algorithm to approximate it with constant performance ratio for any given r and R.