A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs

DOI10.1007/s10878-010-9357-zzbMath1245.90111OpenAlexW2087592368MaRDI QIDQ437046

Weili Wu, Shan Shan, Xu Zhu, Zhong Wang, Wei Wang

Publication date: 17 July 2012

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-010-9357-z

zbMATH Keywords

dominating setmaximal independent setpolynomial time approximation schemeunit disk graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (2)

Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism ⋮ A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks

Cites Work

• A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
• Unit disk graphs
• Approximation algorithms for connected dominating sets
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• Approximation and Online Algorithms

This page was built for publication: A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs