Abstract: The bounded degree maximum spanning sub-graph problem arising from wireless mesh networks was studied. 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 arc 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 sulrnetwork in wireless mesh networks.

Key words: Bounded degree maximum spanning sub-graph,Approximation algorithm,Wireless mesh networks,Transport sub-network selection