Approximation Algorithms for Steiner Connected Dominating Set
Approximation Algorithms for Steiner Connected Dominating Set作者机构: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).