Indian Science Technology and Engineering facilities Map
 
Supplier Map
Service Map

Publications

Publication Details

Applicant:
Indian Institute of Technology (IIT) Patna 
Author:
S. Paul, Arijit Bishnu, Arijit Ghosh 
Corresponding Authors:
Subhabrata Paul 
DOI #:
http://dx.doi.org/10.1016/j.dam.2016.06.008 
Title:
Linear kernels for k-tuple and liar’s domination in bounded genus graphs 
Journal:
Discrete Applied Mathematics 
Year:
2017 
Volume:
231 
Page:
67–77 
Keywords:
k-tuple domination, Liar’s domination, Planar graphs, Bounded genus graphs, Kernelization W[2]-hard 
Abstract:
A set D ⊆ V is called a k-tuple dominating set of a graph G = (V, E) if |NG[v] ∩ D| ≥ k for all v ∈ V, where NG[v] denotes the closed neighborhood of v. A set D ⊆ V is called a liar’s dominating set of a graph G = (V, E) if (i) |NG[v] ∩ D| ≥ 2 for all v ∈ V and (ii) for every pair of distinct vertices u, v ∈ V, |(NG[u] ∪ NG[v]) ∩ D| ≥ 3. Given a graph G, the decision versions of k-Tuple Domination Problem and the Liar’s Domination Problem are to check whether there exist a k-tuple dominating set and a liar’s dominating set of G of a given cardinality, respectively. These two problems are known to be NP-complete (Liao and Chang, 2003; Slater, 2009). In this paper, we study the parameterized complexity of these problems. We show that the k-Tuple Domination Problem and the Liar’s Domination Problem are W[2]-hard for general graphs. It can be verified that both the problems have a finite integer index and satisfy certain coverability property. Hence they admit linear kernel as per the meta-theorem in Bodlaender (2009), but the meta-theorem says nothing about the constant. In this paper, we present a direct proof of the existence of linear kernel with small constants for both the problems. 
Entered by:
Physics Head on 2020-08-04 
 
THE VISION
THE MISSION
ABOUT I-STEM
It has always been the basic tenet of the Government of India, in generously funding R&D efforts at academic institutions over the years, that facilities established through such support be made available to those needing them and qualified to make use of them for their own research work
read more >>

However, this was never easy or straightforward for, among other reasons, there was no ready source of information of what facility was available and where. Thanks to the Web, it is much easier today to have a national and regional “inventory of resources”, so as to match users with the resources they need, and to do all this in an efficient and transparent manner.

This can lead to a leap in R&D productivity and greatly enhance the effectiveness of public investment. This is the motivation behind I-STEM.
read less <<
Visitor Hit Counter
Hosted at Indian Institute of Science
Copyright © 2024 I-STEM. All rights reserved.
Audited by: STQC Bengaluru.