已为您找到该学者19条结果 成果回收站
【期刊论文】Survey of Approximation Algorithm on Virtual Backbone of Wireless Sensor Network
计算机研究与发展,-0001,53(1):15-25
-1年11月30日
Using virtual backbone in wireless sensor network can effectively save energy, reduce interference, and prolong lifetime, which has a wide application in the field of geometric routing and topology control. Virtual backbone can be modeled as a connected dominating set (CDS) in a graph. This paper introduces the state of art of approximation algorithms on CDS and its variations. The focus is put on theoretical results and methods. The purpose is to provide a reference for researchers who are interested in this field.
wireless sensor network (, WSN), ,, virtual backbone,, connected dominating set (, CDS), ,, approximation algorithm,, performance ratio
0
-
33浏览
-
0点赞
-
0收藏
-
0分享
-
0下载
-
0
-
引用
【期刊论文】Eulerian Subgraphs Containing Given Vertices
SIAM J. Discrete Math.,-0001,25(2):611–621
-1年11月30日
A vertex set S⊆V(G) is k-weak-edge-connected if, for every C⊂Sand x∈S−C, there are min{k,|C|} edge-disjoint (x, C)-paths in G. For a graph G and a k-weak-edge-connected vertex set S⊂V(G) with k≥3 and 4≤|S|≤2k, we show that G has an Eulerian subgraph containing all vertices in S.
无
0
-
47浏览
-
0点赞
-
0收藏
-
0分享
-
0下载
-
0
-
引用
【期刊论文】A PTAS for minimum connected dominating set in 3-dimensional Wireless sensor networks
Journal of Global Optimization,2008,45():451–458
2008年12月14日
When homogeneous sensors are deployed into a three-dimensional space instead of a plane, the mathematical model for the sensor network is a unit ball graph instead of a unit disk graph. It is known that for the minimum connected dominating set in unit disk graph, there is a polynomial time approximation scheme (PTAS). However, that construction cannot be extended to obtain a PTAS for unit ball graph. In this paper, we will introduce a new construction, which gives not only a PTAS for the minimum connected dominating set in unit ball graph, but also improves running time of PTAS for unit disk graph.
Wireless sensor network, Connected dominating set, Unit ball graph, PTAS
0
-
22浏览
-
0点赞
-
0收藏
-
0分享
-
0下载
-
0
-
引用
【期刊论文】Optimal placements of replicas in a ring network with majority voting protocol
Journal of Parallel and Distributed Computing,2009,69(5):461-469
2009年05月01日
In a distributed database system, data replicas are placed at different locations to achieve high data availability in the presence of link failures. With a majority voting protocol, a location survives for read/write operations if and only if it is accessible to more than half of the replicas. The problem is to find out the optimal placements for a given number of data replicas in a ring network. When the number of replicas is odd, it was conjectured by Hu et al. [X.-D. Hu, X.-H. Jia, D.-Z. Du, D.-Y. Li, H.-J. Huang, Placement of data replicas for optimal data availability in ring networks, J. Parallel Distrib. Comput., 61 (2001) 1412–1424] that every uniform placement is optimal, which is proved by Shekhar and Wu later. However, when the number of replicas is even, it was pointed out by Hu et al. that uniform placements are not optimal and the optimal placement problem may be very complicated. In this paper, we study the optimal placement problem in a ring network with majority voting protocol and an even number of replicas, and give a complete characterization of optimal placements when the number of replicas is not too large compared with the number of locations.
Optimal placement, Distributed database, Data replica, Majority voting protocol, Ring network
0
-
34浏览
-
0点赞
-
0收藏
-
0分享
-
0下载
-
0
-
引用
【期刊论文】A kind of conditional vertex connectivity of star graphs
Applied Mathematics Letters,2009,22(2):264-267
2009年02月01日
A subset is called an -vertex-cut of if is disconnected and each vertex has at least two neighbors in . The cardinality of a minimum -vertex-cut of , denoted by , is the -vertex-connectivity of . In this work, we prove that for , where is the -dimensional star graph.
Star graph, Conditional vertex connectivity
0
-
42浏览
-
0点赞
-
0收藏
-
0分享
-
0下载
-
0
-
引用
合作学者
- 暂无合作作者