Approximating Bounded Degree Maximum Spanning Subgraphs ∗
Wangsen Feng, Hao Ma, Hanpin Wang · 2014
Abstract The bounded degree maximum spanning subgraph problem arising from wireless mesh networks is studied here. Given a connected graph G and a positive integer d ≥ 2, the problem aims to find a maximum spanning subgraph H of G with the constraint: for every vertex v of G, the degree of v in H, dH(v), is less than or equal to d. Here, a spanning subgraph is a connected subgraph which contains all the vertices of the original graph. We propose polynomial time approximation algorithms for cardinality case and edge weighted case respectively. When input graphs are edge unweighted, a 2-approximation algorithm is designed. When input graphs are edge weighted, the designed algorithm always outputs a spanning subgraph whose maximum degree is no more than OPT (G) d +1 and weight is at least d+2, where OPT (G) is the weight of optimal solutions. The bounded degree spanning subgraph output by the algorithm can be used as a transport subnetwork in wireless mesh networks. 1