Source author record

Ramesh K. Jallu

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Computational Geometry

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Minimum color spanning circle of imprecise points

Let $\cal R$ be a set of $n$ colored imprecise points, where each point is colored by one of $k$ colors. Each imprecise point is specified by a unit disk in which the point lies. We study the problem of computing the smallest and the largest possible minimum color spanning circle, among all possible choices of points inside their corresponding disks. We present an $O(nk\log n)$ time algorithm to compute a smallest minimum color spanning circle. Regarding the largest minimum color spanning circle, we show that the problem is NP-Hard and present a $\frac{1}{3}$ -factor approximation algorithm. We improve the approximation factor to $\frac{1}{2}$ for the case where no two disks of distinct color intersect.

preprint2020arXiv

Liar's Domination in Unit Disk Graphs

In this article, we study a variant of the minimum dominating set problem known as the minimum liar's dominating set (MLDS) problem. We prove that the MLDS problem is NP-hard in unit disk graphs. Next, we show that the recent sub-quadratic time $\frac{11}{2}$ -factor approximation algorithm \cite{bhore} for the MLDS problem is erroneous and propose a simple $O(n + m)$ time 7.31-factor approximation algorithm, where $n$ and $m$ are the number of vertices and edges in the input unit disk graph, respectively. Finally, we prove that the MLDS problem admits a polynomial-time approximation scheme.

preprint2020arXiv

The Generalized Independent and Dominating Set Problems on Unit Disk Graphs

In this article, we study a generalized version of the maximum independent set and minimum dominating set problems, namely, the maximum $d$ -distance independent set problem and the minimum $d$ -distance dominating set problem on unit disk graphs for a positive integer $d>0$ . We first show that the maximum $d$ -distance independent set problem and the minimum $d$ -distance dominating set problem belongs to NP-hard class. Next, we propose a simple polynomial-time constant-factor approximation algorithms and PTAS for both the problems.

preprint2014arXiv

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

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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.