最小权度的网络构建问题

作     者：李睿 吕小俊 

作者机构：云南大学旅游文化学院信息科学与技术系丽江674100 

出 版 物：《现代计算机》 (Modern Computer)

年 卷 期：2012年第18卷第7期

页      码：17-19页

摘      要：网络构建问题是组合最优化中的经典问题,而连通性是网络设计问题中的一个核心问题。考虑这样一个最优化问题:给定无向图G=(V,E;w),w:E→Q^+是权重函数,G =(V,E )为G的一个子图,要寻找E的一个子集E"(?)E,使得由E UE"所得的诱导子图是一个连通图,其目标是使得所有方案中权度最大者的权度值达到最小。经过对问题分析,对问题的特殊情况E =φ,设计了两个时间复杂度分别为O(n^2)和O(mn)的启发式算法,而E"≠φ的情况也可以类似讨论。

主 题 词：网络构建 搜索算法 近似算法 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 070105[070105] 0701[理学-数学类] 

D　O　I：10.3969/j.issn.1007-1423-B.2012.07.004

馆 藏 号：203819219...