Talks and Poster Presentations (with Proceedings-Entry):

S. Banerjee, S. Bhore:
"Algorithm and Hardness Results on Liarīs Dominating Set and k-tuple Dominating Set";
Talk: International Workshop on Combinatorial Algorithms (IWOCA), Pisa; 2019-07-23 - 2019-07-25; in: "IWOCA 2019: Combinatorial Algorithms", LNCS, 11638 (2019), ISBN: 978-3-030-25004-1; 48 - 60.

English abstract:
Given a graph G = (V,E), the dominating set problem asks
for a minimum subset of vertices D ⊆ V such that every vertex u ∈
V \ D is adjacent to at least one vertex v ∈ D. That is, the set D
satisfies the condition that |N[v] ∩ D| ≥ 1 for each v ∈ V , where N[v]
is the closed neighborhood of v. In this paper, we study two variants
of the classical dominating set problem: k-tuple dominating set (k-DS)
problem and Liarīs dominating set (LDS) problem, and obtain several
algorithmic and hardness results. On the algorithmic side, we present a
constant factor ( 11
2 )-approximation algorithm for the Liarīs dominating
set problem on unit disk graphs. Then, we design a polynomial time
approximation scheme (PTAS) for the k-tuple dominating set problem on
unit disk graphs. On the hardness side, we show a Ω(n2) bits lower bound for the space complexity of any (randomized) streaming algorithm for
Liarīs dominating set problem as well as for the k-tuple dominating set problem. Furthermore, we prove that the Liarīs dominating set problem
on bipartite graphs is W[2]-hard.

"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)

Electronic version of the publication:

Created from the Publication Database of the Vienna University of Technology.