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

作     者：凤旺森 张蓓 陈萍 崔健 FENG Wang-sen;ZHANG Bei;CHEN Ping;CUI Jian

作者机构：北京大学计算中心网络与软件安全保障教育部重点实验室北京100871 

基　　金：国家重点基础研究发展计划973(No.2009CB320505)资助 

出 版 物：《计算机科学》 (Computer Science)

年 卷 期：2010年第37卷第3期

页      码：42-45页

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

主 题 词：度数有界最大支撑子图 近似算法 无线网状网络 传输子网选择 

学科分类：081203[081203] 08[工学] 0835[0835] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3969/j.issn.1002-137X.2010.03.008

馆 藏 号：203133326...