A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
type: Item
instance of: scholarly article
title: A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
zbMATH Open document ID: 1162.68042
author: Decheng Dai
author: Chang-Yuan Yu
published in: Theoretical Computer Science
publication date: 2009-03-17T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5529502
zbMATH Keywords: weighted unit disk graph
zbMATH Keywords: dominating set
zbMATH Keywords: approximation algorithm
MaRDI profile type: Publication
full work available at URL: j.tcs.2008.11.015
OpenAlex ID: W2220232453
cites work: Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
cites work: Planar Formulae and Their Uses
cites work: Simple heuristics for unit disk graphs
cites work: NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
cites work: Unit disk graphs
cites work: Q4198056
cites work: On approximation problems related to the independent set and vertex cover problems
cites work: Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
cites work: Q4228484
cites work: Improved methods for approximating node weighted Steiner trees and connected dominating sets.
DOI: 10.1016/J.TCS.2008.11.015
description: scientific article; zbMATH DE number 5529502