PTAS for the minimum weighted dominating set in growth bounded graphs

DOI10.1007/s10898-011-9795-xzbMath1261.90085OpenAlexW1998269424MaRDI QIDQ1928314

Weili Wu, Zhong Wang, Bhavani Thuraisingham, Wei Wang, Joon-Mo Kim

Publication date: 3 January 2013

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

Full work available at URL: https://doi.org/10.1007/s10898-011-9795-x

zbMATH Keywords

approximation algorithmgraph theorydominating setPTAS

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Cites Work

• Unnamed Item
• New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
• A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
• Unit disk graphs
• Unit disk graph recognition is NP-hard
• Algorithmic construction of sets for k -restrictions
• ON MEASURES WITH THE DOUBLING CONDITION
• (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Hausdorff dimension and doubling measures on metric spaces
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Approximation schemes for wireless networks
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs