APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS

DOI10.1142/S021819591350009XMaRDI QIDQ2932520zbMATH OpenFDO

Authors Minati De, Paz Carmi, Gautam K. Das, Subhas C. Nandy

Publication date 1 December 2014

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S021819591350009X

zbMATH Keywords

approximation algorithmminimum dominating setpiercingunit disk

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• Approximation algorithms for the unit disk cover problem in 2D and 3D
• Graph-Theoretic Concepts in Computer Science
• Approximation algorithms for maximum independent set of pseudo-disks
• Approximation algorithms for maximum independent set of pseudo-disks
• On the discrete unit disk cover problem
• On the discrete unit disk cover problem
• Simple linear time algorithms for piercing pairwise intersecting disks
• Approximation Algorithms for Domatic Partitions of Unit Disk Graphs
• Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm
• Linear-time approximation algorithms for unit disk graphs

Cites work

• A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
• A better constant-factor approximation for weighted dominating set in unit disk graph
• Approximation algorithms for maximum independent set of pseudo-disks
• Approximation schemes for covering and packing problems in image processing and VLSI
• Covering a set of points in multidimensional space
• Improved results on geometric hitting set problems
• Minimum clique partition in unit disk graphs
• New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
• On domination and independent domination numbers of a graph
• On the discrete unit disk cover problem
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• Polynomial-time approximation schemes for packing and piercing fat objects
• Polynomial-time approximation schemes for piercing and covering with applications in wireless networks
• Simple heuristics for unit disk graphs
• The NP-completeness column: An ongoing guide
• Unit disk graphs

Cited in

(11)

• Efficient independent set approximation in unit disk graphs
• Approximation algorithms for piercing special families of hippodromes: an extended abstract
• Liar's dominating set problem on unit disk graphs
• Polynomial-time approximation schemes for piercing and covering with applications in wireless networks
• Liar's domination in 2D
• Linear-time approximation algorithms for unit disk graphs
• Minimum dominating set problem for unit disks revisited
• Vertex-edge domination in unit disk graphs
• Simple linear time algorithms for piercing pairwise intersecting disks
• Algorithmic aspects of secure domination in unit disk graphs
• A survey on variant domination problems in geometric intersection graphs

This page was built for publication: APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS

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