Approximation Algorithms for Steiner Connected Dominating Set |
| |
Authors: | Email author" target="_blank">Ya-Feng?WuEmail author Yin-Long?Xu Guo-Liang?Chen |
| |
Affiliation: | (1) 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 |
| |
Abstract: | 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”. |
| |
Keywords: | approximation algorithm Steiner connected dominated set graph algorithm NP-hard |
本文献已被 维普 万方数据 SpringerLink 等数据库收录! |
| 点击此处可从《计算机科学技术学报》浏览原始摘要信息 |
|
点击此处可从《计算机科学技术学报》下载全文 |
|