%0 Journal Article
%T Approximation Algorithms for Steiner Connected Dominating Set
%A Ya-Feng Wu
%A Yin-Long Xu
%A Guo-Liang Chen
%A <br>Ya-Feng Wu
%A Yin-Long Xu
%A and Guo-Liang Chen
%J 计算机科学技术学报
%D 2005
%I 
%X Steiner connected dominating set (SCDS) is a generalization of the famous connected dominating set problem, where only a specified set of required vertices has to be dominated by a connected dominating set, and known to be NP-hard. This paper firstly modifies the SCDS algorithm of Guha and Khuller and achieves a worst case approximation ratio of (2+1/(m 1))H(min (D, k))+O(1), which outperforms the previous best result (c+1)H(min (D, k))+O(1) in the case of mge 1+1/(c 1), where c is the best approximation ratio for Steiner tree, D is the maximum degree of the graph, k is the cardinality of the set of required vertices, m is an optional integer satisfying 0≤ m ≤ min (D, k) and H is the harmonic function. This paper also proposes another approximation algorithm which is based on a greedy approach. The second algorithm can establish a worst case approximation ratio of 2ln (min (D, k))+O(1), which can also be improved to 2ln k if the optimal solution is greater than . Supported by the National Natural Science Foundation of China under Grant No. 60173048 on “Research on Routing and Wavelength Assignment in WDM All-optical Networks”.
%K approximation algorithm
%K Steiner connected dominated set
%K graph algorithm
%K NP-hard<br>渐进算法
%K SCDS
%K 图表法
%K 谐函数
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=5A41B70A3E1F90840C85A9C3E98868A7&yid=2DD7160C83D0ACED&vid=A04140E723CB732E&iid=94C357A881DFC066&sid=A586B761C9AA2FAA&eid=27350781F1397F32&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=0&reference_num=10