Linear-Time Approximation Algorithms for Unit Disk Graphs

DOI10.1007/978-3-319-18263-6_12zbMath1457.68307arXiv1402.4722OpenAlexW96441109MaRDI QIDQ3453289

Guilherme Dias da Fonseca, Celina M. Herrera de Figueiredo, Vinícius G. Pereira de Sá

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

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) 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 (1)

Computing a tree having a small vertex cover

Cites Work

• The complexity of finding fixed-radius near neighbors
• Unit disk graph recognition is NP-hard
• 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
• 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
• Approximation schemes for wireless networks
• Algorithms – ESA 2005
• Unnamed Item
• Unnamed Item

This page was built for publication: Linear-Time Approximation Algorithms for Unit Disk Graphs