Title: (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs
Abstract: 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, Ambühl et al solved this problem by presenting a 72-approximation 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.
Publication Year: 2008
Publication Date: 2008-08-12
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 23
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot