Efficient sub-5 approximations for minimum dominating sets in unit disk graphs

DOI10.1016/j.tcs.2014.01.023zbMath1418.68240arXiv1204.3488OpenAlexW2120272254MaRDI QIDQ2453164

Yanyan Li

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

zbMATH Keywords

dominating setapproximation algorithmsunit disk graph

Mathematics Subject Classification ID

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