版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构: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.