Construction of strongly connected dominating sets in asymmetric multihop wireless networks
Construction of strongly connected dominating sets in asymmetric multihop wireless networks
复制标题
非对称多跳无线网络强连通支配集的构建
DOI：
10.1016/j.tcs.2008.09.058
复制
发表时间：
2009-03
影响因子：
1.1
通讯作者：
Wu, Weili
中科院分区：
文献类型：
--
作者：
Li, Deying;Zhang, Zhao;Wan, Peng-Jun;Gao, Xiaofeng;Du, Hongwei;Wu, Weili
考虑由有向图G=（V，E）表示的非对称无线网络。一个顶点子集U称为强连通控制集（SCDS），如果U诱导的子图是强连通的，并且每个不在U中的顶点在U中既有一个内邻又有一个外邻。SCDS在非对称无线网络中起着虚拟骨干网的重要作用。受小型虚拟骨干网建设的启发，我们研究了最小SCDS问题，即寻找一个有向图的最小SCDS。对于任何常数0<p <1，最小SCDS不存在多项式时间ρ lnn近似，除非NP ≠ DTIME（no（lnn）），其中n是节点数。然而，在文献中提出的最小SCDS的多项式时间算法都不是对数近似。在本文中，我们提出了一个多项式时间（3 H（n−1）−1）-近似算法的最小SCDS，其中H是调和函数。因此，该算法的近似比在任何多项式时间算法可实现的最佳可能近似比的3倍内。
Consider an asymmetric wireless network represented by a digraph G=(V,E). A subset of vertices U is called a strongly connected dominating set (SCDS) if the subgraph induced by U is strongly connected and every vertex not in U has both an in-neighbor in U and an out-neighbor in U. SCDS plays an important role of the virtual backbone in asymmetric wireless networks. Motivated by the construction of a small virtual backbone, we study the problem Minimum SCDS, which seeks a smallest SCDS of a digraph. For any constant 0<ρ<1, there is no polynomial-time ρlnn-approximation for Minimum SCDS unless NP⊆DTIME(no(lnn)), where n is the number of nodes. However, none of the polynomial-time heuristics for Minimum SCDS proposed in the literature are logarithmic approximations. In this paper, we present a polynomial-time (3H(n−1)−1)-approximation algorithm for Minimum SCDS, where H is the harmonic function. The approximation ratio of this algorithm is thus within a factor of 3 from the best possible approximation ratio achievable by any polynomial-time algorithm.
登录
查看更多内容
DOI：
10.1109/icpp.2001.952059
发表时间：
2001-09
期刊：
International Conference on Parallel Processing, 2001.
影响因子：
--
作者：
A. Salhieh;J. Weinmann;Manish Kochhal;L. Schwiebert
通讯作者：
A. Salhieh;J. Weinmann;Manish Kochhal;L. Schwiebert
DOI：
10.1007/b102533
发表时间：
2013
期刊：
Springer US
影响因子：
--
作者：
通讯作者：
--
DOI：
10.1007/978-1-4613-0303-9
发表时间：
1998-10
期刊：
--
影响因子：
--
作者：
D. Du;P. Pardalos
通讯作者：
D. Du;P. Pardalos
影响因子：
3.8
作者：
P. Wan;K. Alzoubi;O. Frieder
通讯作者：
P. Wan;K. Alzoubi;O. Frieder
DOI：
10.1007/11610113_2
发表时间：
2006-01
期刊：
--
影响因子：
--
作者：
D. Du;M. Thai;Yingshu Li;Dan Liu;Shiwei Zhu
通讯作者：
D. Du;M. Thai;Yingshu Li;Dan Liu;Shiwei Zhu