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.
| Original language | English |
|---|---|
| Pages (from-to) | 198-208 |
| Number of pages | 11 |
| Journal | Theoretical Computer Science |
| Volume | 412 |
| Issue number | 3 |
| DOIs | |
| State | Published - 21 Jan 2011 |
| Externally published | Yes |
Keywords
- Approximation algorithm
- Minimum-weighted chromatic disk cover
- Minimum-weighted connected dominating set
- Minimum-weighted dominating set
- Node-weighted Steiner tree
- Polynomial-time approximation scheme
Fingerprint
Dive into the research topics of 'New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver