New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
type: Item
instance of: scholarly article
title: New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
zbMATH Open document ID: 1209.68389
author: Feng Zou
author: Yuexuan Wang
author: Xiao-Hua Xu
author: Xianyue Li
author: Weili Wu
author: Hongwei Du
author: Peng-Jun Wan
published in: Theoretical Computer Science
publication date: 2011-01-28T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5842800
zbMATH Keywords: minimum-weighted dominating set
zbMATH Keywords: minimum-weighted connected dominating set
zbMATH Keywords: minimum-weighted chromatic disk cover
zbMATH Keywords: node-weighted Steiner tree
zbMATH Keywords: polynomial-time approximation scheme
zbMATH Keywords: approximation algorithm
MaRDI profile type: Publication
full work available at URL: j.tcs.2009.06.022
OpenAlex ID: W2155234080
cites work: Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: Approximations for Steiner trees with minimum number of Steiner points
cites work: A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
cites work: Q4198056
cites work: Improved methods for approximating node weighted Steiner trees and connected dominating sets.
cites work: Approximation schemes for covering and packing problems in image processing and VLSI
cites work: Steiner tree problems
cites work: Planar Formulae and Their Uses
cites work: The broadcast storm problem in a mobile ad hoc network
cites work: An approximation scheme for some Steiner tree problems in the plane
cites work: Minimum connected dominating sets and maximal independent sets in unit disk graphs
cites work: Node-weighted Steiner tree approximation in unit disk graphs
DOI: 10.1016/J.TCS.2009.06.022
description: scientific article; zbMATH DE number 5842800