Read full paper at: http://www.scirp.org/journal/PaperInformation.aspx?PaperID=53574#.VMnXsCzQrzE Author(s) Chuan-Min Lee 1 , Cheng-Chien Lo 1 , Rui-Xin Ye 2 , Xun Xu 2 , Xiao-Han Shi 2 , Jia-Ying Li 2 Affiliation(s) 1 Department of Computer and Communication Engineering, Ming Chuan University, The First American University in Asia, Taoyuan, Taiwan, Chinese Taipei . 2 Department of Electronic Information Engineering, Fuzhou University, Fuzhou, China . ABSTRACT This paper is motivated by the concept of the signed k-domination problem and dedicated to the complexity of the problem on graphs. For any fixed nonnegative integer k, we show that the signed k-domination problem is NP-complete for doubly chordal graphs. For strongly chordal graphs and distance-hereditary graphs, we show that the signed k-domination problem can be solved in polynomial time. We also show that the problem is linear-time solvable for trees, interval graphs, and chord...
评论
发表评论