Given a graph G with vertex set V, a set S⊆ V is a secure dominating set of G if S is a
dominating set of G and if for every vertex u∈ V∖ S, there exists a vertex v∈ S adjacent to u …

Abstract Let G=(V, E) be a unit disk graph corresponding to a given set P of n points in R 2.
We propose a distributed approximation algorithm to find a minimum connected dominating …

Abstract Let G=(V, E) be a simple undirected graph. A set D⊆ V is called a vertex-edge
dominating set of G if for each edge e= uv∈ E, either u or v is in D or one vertex from their …

We consider the maximum (weight) independent set problem in unit disk graphs. The high
complexity of the existing polynomial-time approximation schemes motivated the …

In this article, we study approximation algorithms for the problem of computing minimum
dominating set for a given set S of n unit disks in ℝ 2. We first present a simple O (n log k) …

We study several variations of line segment covering problem with axis-parallel unit squares
in the plane. Given a set S of n line segments, the objective is to find the minimum number of …

Given a graph G with vertex set V, a subset S of V is called a dominating set of G if every
vertex is either in S or is adjacent to a vertex in S. There are a lot of variants for dominating …

Numerous approximation algorithms for problems on unit disk graphs have been proposed
in the literature, exhibiting a sharp trade-off between running times and approximation ratios …

We study several variations of line segment covering problem with axis-parallel unit squares
in the plane. Given a set S of n line segments, the objective is to find the minimum number of …

In this paper, we consider Euclidean versions of the 2-tuple dominating set problem and the
liar's dominating set problem. For a given set P={p 1, p 2,…, pn} of n points in R 2, the …