咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >New approximations for minimum... 收藏

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.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分