Computer Science ›› 2007, Vol. 34 ›› Issue (1): 177-178.
Previous Articles Next Articles
LI Zhen-Jian, GE Qi ,WANG Hai-Tao ,ZHU Hong （Dept. of Computer Science and Engineering, Fudan University,Shanghai 200433）
Online:
Published:
Abstract: Two variations of the dominating set problem are presented, both of which have corresponding application background. In this paper, we prove the decision problems of the two variations are NPC. Furthermore, the approximation algorithms for their col-respo
Key words: Dominating set problem, Cstrong dominating set problem, Compl.ete dominating set problem, NPC, NP- hard, Approximation algorithm
LI Zhen-Jian, GE Qi ,WANG Hai-Tao ,ZHU Hong （Dept. of Computer Science and Engineering, Fudan University,Shanghai 200433）. [J].Computer Science, 2007, 34(1): 177-178.
0 / / Recommend
Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks
URL: https://www.jsjkx.com/EN/
https://www.jsjkx.com/EN/Y2007/V34/I1/177
Cited
Home