Linear-time approximation algorithms for unit disk graphs

DOI10.1007/978-3-319-18263-6_12zbMATH Open1457.68307arXiv1402.4722OpenAlexW96441109MaRDI QIDQ3453289FDOQ3453289

Authors: Guilherme D. Da Fonseca, Vinícius G. P. De Sá, Celina M. H. de Figueiredo 

Publication date: 20 November 2015

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Abstract: Numerous approximation algorithms for problems on unit disk graphs have been proposed in the literature, exhibiting a sharp trade-off between running times and approximation ratios. We introduce a variation of the known shifting strategy that allows us to obtain linear-time constant-factor approximation algorithms for such problems. To illustrate the applicability of the proposed variation, we obtain results for three well-known optimization problems. Among such results, the proposed method yields linear-time (4+eps)-approximation for the maximum-weight independent set and the minimum dominating set of unit disk graphs, thus bringing significant performance improvements when compared to previous algorithms that achieve the same approximation ratios. Finally, we use axis-aligned rectangles to illustrate that the same method may be used to derive linear-time approximations for problems on other geometric intersection graph classes.

Full work available at URL: https://arxiv.org/abs/1402.4722

Recommendations

• Linear time approximation for dominating sets and independent dominating sets in unit disk graphs
• Shifting coresets: obtaining linear-time approximations for unit disk graphs and other geometric intersection graphs
• Efficient independent set approximation in unit disk graphs
• Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
• A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Unit disk graph recognition is NP-hard
• Approximation schemes for covering and packing problems in image processing and VLSI
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Simple heuristics for unit disk graphs
• Algorithms – ESA 2005
• Title not available (Why is that?)
• Approximation schemes for wireless networks
• The complexity of finding fixed-radius near neighbors
• Title not available (Why is that?)
• Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
• APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS

Cited In (10)

• Linear time approximation for dominating sets and independent dominating sets in unit disk graphs
• ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs
• Approximation Algorithms for Domatic Partitions of Unit Disk Graphs
• Plane hop spanners for unit disk graphs: simpler and better
• An Almost Linear Time 2.8334-Approximation Algorithm for the Disc Covering Problem
• Shifting coresets: obtaining linear-time approximations for unit disk graphs and other geometric intersection graphs
• Approximating 2-cliques in unit disk graphs
• Simple heuristics for unit disk graphs
• Approximate Distance Queries in Disk Graphs
• APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS

This page was built for publication: Linear-time approximation algorithms for unit disk graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3453289)