计算机科学 ›› 2010, Vol. 37 ›› Issue (3): 42-45.

• 计算机网络与信息安全 • 上一篇    下一篇

传输子网选择:度数有界最大支撑子图逼近

凤旺森,张蓓,陈萍,崔健   

  1. (北京大学计算中心网络与软件安全保障教育部重点实验室 北京100871)
  • 出版日期:2018-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受国家重点基础研究发展计划973 (No. 2009CB320505)资助。

Transport Sub-network Selection:Approaching with Bounded Maximum Spanning Sub-graphs

FENG Wang-sen,ZHANG Bei,CHEN Ping,CUI Jian   

  • Online:2018-12-01 Published:2018-12-01

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

关键词: 度数有界最大支撑子图,近似算法,无线网状网络,传输子网选择

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

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!