A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs
From MaRDI portal
Publication:3558921
DOI10.1007/978-3-642-12450-1_13zbMath1284.68663OpenAlexW1579968022MaRDI QIDQ3558921
Matúš Mihalák, Erlebach, Thomas
Publication date: 11 May 2010
Published in: Approximation and Online Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-12450-1_13
Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items (9)
On pseudo-disk hypergraphs ⋮ A PTAS for the Weighted Unit Disk Cover Problem ⋮ Constant Approximation for the Lifetime Scheduling Problem of p-Percent Coverage ⋮ Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph ⋮ Improved solution to data gathering with mobile mule ⋮ Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set ⋮ Efficient sub-5 approximations for minimum dominating sets in unit disk graphs ⋮ Sensor Cover and Double Partition ⋮ Constant-approximation for minimum weight partial sensor cover
This page was built for publication: A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs
