(6+∈)-Approzimation for Minimum Weight Dominating Set in Unit Disk Graphs

摘要：

It was a long-standing open problem whether the minimum weight dominating set in unit disk graphs has a polynomial-time constant-approximation. In 2006, Ambiihl et al solved this problem by presenting a 72approximation for the minimum weight dominating set and also a 89-approximation for the minimum weight connected dominating set in unit disk graphs. In this paper, we improve their results by giving a (6 + ∈)approximation for the minimum weight dominating set and a (10 + ∈)-approximation for the minimum weight connected dominating set in unit disk graphs where ∈ is any small positive number.

关键词： Unit Disk Graph Approzimation algorithm Dominating Set

作者: Xiaofeng Gao Yaochun Huang Zhao Zhang Weili Wu

作者单位: Department of Computer Science, University of Texas at Dallas,USA Department of Computer Science, University of Texas at Dallas, USA College of Mathematics and System Sciences,Xingjiang University, China

会议类型: 国际会议

会议名称: The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)

会议地点: 大连

会议语种:英文

页码: 551-557

在线出版日期: 2008-06-01（万方平台首次上网日期，不代表论文的发表时间）