New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs |
| |
| Authors: | Feng Zou Yuexuan Wang Hongwei Du |
| |
| Affiliation: | a Department of Computer Science, University of Texas at Dallas, Richardson, TX 75080, USAb Institute of Theoretical Computer Science, Tsinghua University, Beijing 100084, Chinac Department of Computer Science, Illinois Institute of Technology, Chicago, IL 60616, USAd School of Mathematics and Statistics, Lanzhou University, Lanzhou, Gansu 730000, China |
| |
| Abstract: | 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 +ε)-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 +ε)-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 +ε)-approximation algorithm for an MWCDS. |
| |
| Keywords: | Minimum-weighted dominating set Minimum-weighted connected dominating set Minimum-weighted chromatic disk cover Node-weighted Steiner tree Polynomial-time approximation scheme Approximation algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
