کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427605 | 686528 | 2012 | 7 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Algorithmic aspects of k-tuple total domination in graphs Algorithmic aspects of k-tuple total domination in graphs](/preview/png/427605.png)
For a fixed positive integer k, a k-tuple total dominating set of a graph G=(V,E)G=(V,E) is a subset TDkTDk of V such that every vertex in V is adjacent to at least k vertices of TDkTDk. In minimum k-tuple total dominating set problem (Mink-Tuple Total Dom Set), it is required to find a k-tuple total dominating set of minimum cardinality and Decide Mink-Tuple Total Dom Set is the decision version of Mink-Tuple Total Dom Set problem. In this paper, we show that Decide Mink-Tuple Total Dom Set is NP-complete for split graphs, doubly chordal graphs and bipartite graphs. For chordal bipartite graphs, we show that Mink-Tuple Total Dom Set can be solved in polynomial time. We also propose some hardness results and approximation algorithms for Mink-Tuple Total Dom Set problem.
► We study on algorithmic aspects of the problem of finding minimum k -tuple total dominating set.
► We prove that for any k>0k>0, the problem of finding minimum k-tuple total dominating set is NP-hard for split graphs and bipartite graphs.
► We show that a minimum k-tuple total dominating set can be found for chordal bipartite graphs in polynomial time.
► We present some hardness and approximation results on the problem of finding minimum k-tuple total dominating set.
Journal: Information Processing Letters - Volume 112, Issue 21, 15 November 2012, Pages 816–822