2012/08/02 by Xiaohua Xu, Xu, Xiaohua, Xiang-Yang Li +1
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI) #cs.DS #cs.NI
paper · pdf · doi:10.48550/arxiv.1208.5738
8 pages, 4 figures, 2 tables
arxiv created 2012/08/02 · arxiv updated 2015/03/20
Considering a communication topology of a wireless network modeled by a graph where an edge exists between two nodes if they are within each other's communication range. A subset U of nodes is a dominating set if each node is either in U or adjacent to some node in U. Assume each node has a disparate communication range and is associated with a positive weight, we present a randomized algorithm to find a min-weight dominating set. Considering any orientation of the graph where an arc \overrightarrowuv exists if the node v lies in u's communication range. A subset U of nodes is a strongly dominating set if every node except U has both in-neighbor(s) and out-neighbor(s) in U. We present a polynomial-time algorithm to find a strongly dominating set of size at most (2+ε) times of the optimum. We also investigate another related problem called K-Coverage. Given are a set \cal D of disks with positive weight and a set \cal P of nodes. Assume all input nodes lie below a horizontal line l and all input disks lie above this line l in the plane. The objective is to find a min-weight subset \cal D'⊆ \cal D of disks such that each node is covered at least K disks in \cal D'. We propose a novel two-approximation algorithm for this problem.