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

【Abstract】 The bounded degree maximum spanning sub-graph problem arising from wireless mesh networks was stu-died.Given a connected graph G=(V,E) and a positive integer d≥2,the problem aims to find a maximum spanning sub-graph H of G with the constraint:for each vertex v∈V,the degree of v in H,dH(v)≤d.Here,a spanning sub-graph of G is a connected sub-graph in G which contains all the vertices of G.Polynomial time approximation algorithms were proposed for edge un-weighted case and edge weighted case respectively.When input graphs are edge un-weighted,a 2-approximation algorithm is designed.When input graphs are edge weighted,the designed algorithm always outputs a spanning sub-graph whose maximum degree is no more than d+1 and weight is at least OPT(G)d+2,where OPT(G) is the weight of optimal solutions.The bounded degree spanning sub-graph output by the algorithm can be used as a transport sub-network in wireless mesh networks.更多还原