近似2-连通k-支配容错虚拟主干网 (2009年)

由于无线网络存在节点失效、链路断裂等特性，虚拟主干网需要具备一定的容错性。利用2-连通k-支配集作为容错虚拟主干网的模型。通过分析单位圆盘图中极大独立集的性质和连通图的块一割点树结构，首次设计出在无线自组织网络中构造2-连通k-支配虚拟主干网的近似算法。从理论上分析了该算法的时间复杂度，并证明了该算法的近似比为常数。