Paper Info
Title
Complexity of total {k}-domination and related problems
Abstract
In this paper, we study the {k}-domination, total {k}-domin-ation, {k}-domatic number, and total {k}-domatic number problems, from complexity and algorithmic points of view. Let k ≥ 1 be a fixed integer and ε > 0 be any constant. Under the hardness assumption of NP Ë</font > eq DTIME(nO(loglogn))NP\not\subseteq DTIME(n^{O(\log\log n)}), we obtain the following results. 1  The total {k}-domination problem is NP-complete even on bipartite graphs. 2  The total {k}-domination problem has a polynomial time ln n approximation algorithm, but cannot be approximated within (\frac1k-</font >e</font >)lnn(\frac{1}{k}-\epsilon)\ln n in polynomial time. 3  The total {k}-domatic number problem has a polynomial time (\frac1k+e</font >)lnn(\frac{1}{k}+\epsilon)\ln n approximation algorithm, but does not have any polynomial time (\frac1k-</font >e</font >)lnn(\frac{1}{k}-\epsilon)\ln n approximation algorithm. All our results hold also for the non-total variants of the problems.
Year
DOI
Venue
2011
10.1007/978-3-642-21204-8_18
FAW-AAIM
Keywords
Field
DocType
log log n,algorithmic point,polynomial time ln n,domatic number,domination problem,related problem,lnn approximation algorithm,polynomial time,approximation algorithm,ln n,domatic number problem
Log-log plot,Integer,DTIME,Discrete mathematics,Approximation algorithm,Combinatorics,Bipartite graph,Number problem,Domination analysis,Time complexity,Mathematics
Conference
Volume
ISSN
Citations 
6681
0302-9743
1
PageRank 
References 
Authors
0.36
9
2
Name
Order
Citations
PageRank
Jing He1222.67
Hongyu Liang28416.39