# Minimum Dominating Set for a Point Set in $\\IR^2$

Source: [Minimum Dominating Set for a Point Set in $\\IR^2$](<https://www.sota2.com/research/paper/68fa61321e209131ce9f3341>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T19:54:34.816Z

Authors: Ramesh K. Jallu, Prajwal R. Prasad, Gautam K. Das

Published: 2013-12-27T11:09:37.000Z

## Abstract

In this article, we consider the problem of computing minimum dominating set for a given set $S$ of $n$ points in $\\IR^2$. Here the objective is to find a minimum cardinality subset $S'$ of $S$ such that the union of the unit radius disks centered at the points in $S'$ covers all the points in $S$. We first propose a simple 4-factor and 3-factor approximation algorithms in $O(n^6 \\log n)$ and $O(n^{11} \\log n)$ time respectively improving time complexities by a factor of $O(n^2)$ and $O(n^4)$ respectively over the best known result available in the literature \[M. De, G.K. Das, P. Carmi and S.C. Nandy, {\\it Approximation algorithms for a variant of discrete piercing set problem for unit disk}, Int. J. of Comp. Geom. and Appl., to appear\]. Finally, we propose a very important shifting lemma, which is of independent interest and using this lemma we propose a $\\frac{5}{2}$-factor approximation algorithm and a PTAS for the minimum dominating set problem.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1312.7243>)

[PDF](<https://arxiv.org/pdf/1312.7243.pdf>)
