摘要：在无线自组织网络中，经常选取一些节点形成虚拟主干网，用以支持路由和区域监视等任务。由于无线网络自身存在误码率高、易受干扰等弱点，虚拟主干网需要具有一定的容错性。已经有研究者提出使用k-连通k-支配集合在无线自组织网络中构造容错虚拟主干网，并通过模拟实验评估了算法的性能。近年来，Wang Feng等人设计了常数近似算法用来构造2-连通虚拟主干网。本文将设计一个常数近似算法用以在无线自组织网络中构造一个2-连通k-支配虚拟主干网。

关键词：近似算法 无线自组织网络 虚拟主干网 

单位：北京大学信息科学技术学院软件研究所 北京100871 高可信软件技术教育部重点实验室 北京100871