Approzimating Bounded Degree Mazimum Spanning Subgraphs

摘要：

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 d+1 and weight is at least OPT(G)/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.

作者: Wangsen Feng Hao Ma Bei Zhang Hanpin Wang

作者单位: Key Laboratory of Network and Software Security Assurance, Ministry of Education Computing Center, P School of EECS, Peking University, Beijing 100871, P.R. China

会议类型: 国际会议

会议名称: The 8th International Symposium on Operations Research and Its Applications(第八届运筹及其应用国际专题讨论会 ISORA09)

会议地点: 张家界

会议语种:英文

页码: 83-89

在线出版日期: 2009-09-20（万方平台首次上网日期，不代表论文的发表时间）