Efficient independent set approximation in unit disk graphs

DOI10.1016/j.dam.2018.05.049zbMath1439.05176OpenAlexW2809347089WikidataQ129651536 ScholiaQ129651536MaRDI QIDQ2181244

Gautam K. Das, Ramesh K. Jallu, Guilherme Dias da Fonseca

Publication date: 18 May 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2018.05.049

zbMATH Keywords

approximation algorithmsmaximum independent setpolynomial-time approximation schemeunit disk graph

Mathematics Subject Classification ID

Analysis of algorithms (68W40) 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)

Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Tight lower bounds for halfspace range searching
• Optimal partition trees
• Approximation algorithms for maximum independent set of pseudo-disks
• Approximation algorithms for maximum independent set of a unit disk graph
• How hard is half-space range searching?
• Worst-case optimal insertion and deletion methods for decomposable searching problems
• Unit disk graphs
• Label placement by maximum independent set in rectangles
• 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
• Minimum Dominating Set Problem for Unit Disks Revisited
• A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries
• Approximation schemes for covering and packing problems in image processing and VLSI
• Decomposable searching problems I. Static-to-dynamic transformation
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Simple heuristics for unit disk graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Approximation schemes for wireless networks
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Efficient independent set approximation in unit disk graphs