Linear-Time Approximation Algorithms for Unit Disk Graphs
Publication:3453289
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
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)
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