Efficient independent set approximation in unit disk graphs

DOI10.1016/J.DAM.2018.05.049MaRDI QIDQ2181244zbMATH OpenOpenAlexWikidataFDO

Authors Gautam K. Das, Ramesh K. Jallu, Guilherme D. 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 algorithmspolynomial-time approximation schememaximum independent setunit disk graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Faster approximation for maximum independent set on unit disk graph
• Approximation algorithms for maximum independent set of a unit disk graph
• Linear time approximation for dominating sets and independent dominating sets in unit disk graphs
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 1182757
• Approximating independent sets in sparse graphs
• scientific article; zbMATH DE number 1696627
• Approximation algorithms for independent sets in map graphs
• Improved algorithm for maximum independent set on unit disk graph
• Improved approximations of independent sets in bounded-degree graphs

Cites work

• scientific article; zbMATH DE number 1507300 (Why is no real title available?)
• A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
• Approximation algorithms for maximum independent set of a unit disk graph
• Approximation algorithms for maximum independent set of pseudo-disks
• Approximation schemes for covering and packing problems in image processing and VLSI
• Approximation schemes for wireless networks
• Computational geometry. Algorithms and applications.
• Decomposable searching problems I. Static-to-dynamic transformation
• Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
• Graph-Theoretic Concepts in Computer Science
• How hard is half-space range searching?
• Label placement by maximum independent set in rectangles
• Minimum dominating set problem for unit disks revisited
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Optimal partition trees
• Polynomial-time approximation schemes for packing and piercing fat objects
• Simple heuristics for unit disk graphs
• Tight lower bounds for halfspace range searching
• Unit disk graphs
• Worst-case optimal insertion and deletion methods for decomposable searching problems

Cited in

(19)

• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• scientific article; zbMATH DE number 1696627 (Why is no real title available?)
• Maximum area independent sets in disk intersection graphs
• Approximation algorithms for maximum independent set of pseudo-disks
• Distributed Approximations for Packing in Unit-Disk Graphs
• Approximation algorithms for independent sets in map graphs
• Approximation Algorithms for Geometric Intersection Graphs
• Shifting coresets: obtaining linear-time approximations for unit disk graphs and other geometric intersection graphs
• scientific article; zbMATH DE number 1507300 (Why is no real title available?)
• Improved algorithm for maximum independent set on unit disk graph
• Minimum clique partition in unit disk graphs
• Approximation algorithms for maximum independent set of a unit disk graph
• Faster approximation for maximum independent set on unit disk graph
• The maximum distance-d independent set problem on unit disk graphs
• Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
• Approximation algorithms for maximum independent set of pseudo-disks
• Linear-time approximation algorithms for unit disk graphs
• Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs
• Graph-Theoretic Concepts in Computer Science

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

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