传输子网选择:度数有界最大支撑子图逼近

摘要：

研究了源于无线网状网络的度数有界最大支撑子图问题:给定连通图G=(V,E)和正整数d≥2,求G的一个最大支撑子图H,满足对V中每个顶点v,v在H中的度数dH(v)不超过d.这里,支撑子图指图G的一个连通而且包括G中所有顶点的子图.就输入图的边是否带权,分别设计了多项式时间近似算法.当输入图为无权图时,证明了近似算法的近似比为2;当输入图为赋权图时,证明了算法输出一个最大度数不超过d+1、权重不低于最优解权重1/(d+2)的支撑子图.算法输出的度数有界支撑子图可以用作无线网状网络的传输子网.

关键词：度数有界最大支撑子图、近似算法、无线网状网络、传输子网选择

所属期刊栏目：37

分类号：TP391(计算技术、计算机技术)

资助基金：国家重点基础研究发展计划9732009CB320505

在线出版日期：2010-05-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：42-45