Linear-time approximation algorithms for unit disk graphs

DOI10.1007/978-3-319-18263-6_12MaRDI QIDQ3453289zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(11)

• 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
• Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
• Plane hop spanners for unit disk graphs: simpler and better
• Approximation Algorithms for Domatic Partitions of Unit Disk Graphs
• 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)