基于相邻矩阵快速构建虚拟主干网的近似算法

在无线ad-hoc网络中，基于极小连通支配集的虚拟主干网技术对资源分配和路由优化具有重要的作用。首先证明了相部矩阵理论的一个有关结论，然后利用此结论以及极大独立集和极小支配集的关系，提出了一种基于相部矩阵快速构建无线ad-hoc网络最小连通支配集的近似算法，并给出了算法的正确性证明、复杂性分析和近似比分析。仿真试验结果表明，利用该算法可以快速高效地构建ad-hoc网络的虚拟主干网。