New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs

作     者：Zou, Feng Wang, Yuexuan Xu, Xiao-Hua Li, Xianyue Du, Hongwei Wan, Pengjun Wu, Weili 

作者机构：Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA Tsinghua Univ Inst Theoret Comp Sci Beijing 100084 Peoples R China IIT Dept Comp Sci Chicago IL 60616 USA Lanzhou Univ Sch Math & Stat Lanzhou 730000 Gansu Peoples R China 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2011年第412卷第3期

页      面：198-208页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Division of Computing and Communication Foundations Direct For Computer & Info Scie & Enginr Funding Source: National Science Foundation 

主　　题：Minimum-weighted dominating set Minimum-weighted connected dominating set Minimum-weighted chromatic disk cover Node-weighted Steiner tree Polynomial-time approximation scheme Approximation algorithm 

摘      要：Given a node-weighted graph, the minimum-weighted dominating set (MWDS) problem is to find a minimum-weighted vertex subset such that, for any vertex, it is contained in this subset or it has a neighbor contained in this set. And the minimum-weighted connected dominating set (MWCDS) problem is to find a MWDS such that the graph induced by this subset is connected. In this paper, we study these two problems on a unit disk graph. A (4 +epsilon)-approximation algorithm for an MWDS based on a dynamic programming algorithm for a Min-Weight Chromatic Disk Cover is presented. Meanwhile, we also propose a (1 +epsilon)-approximation algorithm for the connecting part by showing a polynomial-time approximation scheme for a Node-Weighted Steiner Tree problem when the given terminal set is c-local and thus obtain a (5 +epsilon)-approximation algorithm for an MWCDS. (C) 2009 Elsevier B.V. All rights reserved.