| 传输子网选择:度数有界最大支撑子图逼近 |
| |
| 引用本文： | 凤旺森,张蓓,陈萍,崔健.传输子网选择:度数有界最大支撑子图逼近[J].计算机科学,2010,37(3):42-45. |
| |
| 作者姓名： | 凤旺森 张蓓 陈萍 崔健 |
| |
| 作者单位： | 北京大学计算中心网络与软件安全保障教育部重点实验室,北京,100871 |
| |
| 基金项目： | 国家重点基础研究发展计划973(No.2009CB320505)资助 |
| |
| 摘 要： | 研究了源于无线网状网络的度数有界最大支撑子图问题:给定连通图G=(V,E)和正整数d≥2,求G的一个最大支撑子图H,满足对V中每个顶点v,v在H中的度数dH(v)不超过d。这里,支撑子图指图G的一个连通而且包括G中所有顶点的子图。就输入图的边是否带权,分别设计了多项式时间近似算法。当输入图为无权图时,证明了近似算法的近似比为2;当输入图为赋权图时,证明了算法输出一个最大度数不超过d+1、权重不低于最优解权重1/(d+2)的支撑子图。算法输出的度数有界支撑子图可以用作无线网状网络的传输子网。
|
| 关 键 词： | 度数有界最大支撑子图 近似算法 无线网状网络 传输子网选择 |
| 收稿时间： | 4/9/2009 12:00:00 AM |
| 修稿时间： | 2009/6/16 0:00:00 |
Transport Sub-network Selection:Approaching with Bounded
Maximum Spanning Sub-graphs |
| |
| 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. |
| |
| Authors: | FENG Wang-sen ZHANG Bei CHEN Ping CUI Jian |
| |
| Affiliation: | Key Laboratory of Network and Software Security Assurance of Ministry of Education/a>;Computing Center/a>;Peking University/a>;Beijing 100871/a>;China |
| |
| 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, d_H(v)≤d. Here, a spanning subgraph 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 arid 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. |
| |
| Keywords: | Bounded degree maximum spanning sub-graph Approximation algorithm Wireless mesh networks Transport sub-network selection |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
|
