Approximation Algorithms for Steiner Connected Dominating Set

作     者：Ya-Feng Wu Yin-Long Xu Guo-Liang Chen 

作者机构：National High Performance Computing Center at Hefei Department of Computer Science and Technology University of Science and Technology of China Hefei 230027 P.R. China 

出 版 物：《Journal of Computer Science & Technology》 (计算机科学技术学报（英文版）)

年 卷 期：2005年第20卷第5期

页      面：713-716页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

基　　金：国家自然科学基金 'Research on Routing and Wave length assignment in WDM All-optical Networks' 

主　　题：approximation algorithm Steiner connected dominated set graph algorithm NP-hard 

摘      要：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（△, k）） ＋O（1）, which outperforms the previous best result （c ＋ 1）H（min（△, k）） ＋ O（1） in the case of m ≥ 1 ＋1/（c - 1）, where c is the best approximation ratio for Steiner tree, A 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（△, 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 2 ln（min（△, k）） ＋ O（1）, which can also be improved to 2 lnk if the optimal solution is greater than c·e^2c＋1/2（c＋1）.