在无线传感器网络中应用虚拟骨干，可以有效地节约能量、减少干扰、延长网络寿命，在几何路由算法和网络拓扑控制等方面具有广泛的应用.虚拟骨干可以模型化为图中的连通控制集.主要从近似算法角度介绍连通控制集及其各种变形在国内外的研究现状及最新进展，侧重于研究方法和理论结果，为相关研究人员提供参考.

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.

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.

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.

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.