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