Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
From MaRDI portal
Publication:2453164
DOI10.1016/j.tcs.2014.01.023zbMath1418.68240arXiv1204.3488OpenAlexW2120272254MaRDI QIDQ2453164
Publication date: 6 June 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1204.3488
Analysis of algorithms (68W40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (9)
Linear-Time Approximation Algorithms for Unit Disk Graphs ⋮ Approximating maximum diameter-bounded subgraph in unit disk graphs ⋮ Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs ⋮ Efficient independent set approximation in unit disk graphs ⋮ Algorithmic aspects of secure domination in unit disk graphs ⋮ Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs ⋮ On the recognition of unit disk graphs and the distance geometry problem with ranges ⋮ Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph ⋮ On forbidden induced subgraphs for unit disk graphs
Cites Work
- Unnamed Item
- Unnamed Item
- New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
- Approximating minimum independent dominating sets in wireless networks
- Unit disk graphs
- The complexity of finding fixed-radius near neighbors
- Unit disk graph recognition is NP-hard
- Efficient graph representations
- The densest packing of 13 congruent circles in a circle
- Integer realizations of disk and segment graphs
- A linear-time approximation algorithm for weighted matchings in graphs
- Parameterized Complexity of Independence and Domination on Geometric Graphs
- A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs
- Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Simple heuristics for unit disk graphs
- Approximation schemes for wireless networks
- Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
This page was built for publication: Efficient sub-5 approximations for minimum dominating sets in unit disk graphs