Advertisement
Published in:
2008 | OriginalPaper | Chapter
Double Partition: (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs
Author : Ding-Zhu Du
Published in: Algorithmic Aspects in Information and Management
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We introduce a new technique on partition, called double partition. With this new type of partition, we obtain a polynomial time (6 +
ε
)-approximation (
ε
> 0) for the minimum weight dominating set problem in unit disk graphs, which improves a recent result of a 72-approximation given by Ambühl et al. for solving a long-standing open problem. As a corollary, we obtain a (9.875 +
ε
)-approximation for the minimum weight connected dominating set problem in unit disk graphs.