摘要: 研究了源于无线网状网络的度数有界最大支撑子图问题:给定连通图G=(V,E)和正整数d>2,求G的一个最大支撑子图H,满足对V中每个顶点二,v在H中的度数dH(v)不超过d。这里,支撑子图指图G的一个连通而且包括G中所有顶点的子图。就输入图的边是否带权,分别设计了多项式时间近似算法。当输入图为无权图时,证明了近似算法的近似比为2;当输入图为赋权图时,证明了算法输出一个最大度数不超过d+1、权重不低于最优解权重1/
凤旺森,张蓓,陈萍,崔健. 传输子网选择:度数有界最大支撑子图逼近[J]. 计算机科学, 2010, 37(3): 42-45. https://doi.org/
FENG Wang-sen,ZHANG Bei,CHEN Ping,CUI Jian. Transport Sub-network Selection:Approaching with Bounded
Maximum Spanning Sub-graphs[J]. Computer Science, 2010, 37(3): 42-45. https://doi.org/