瓶颈Steiner树问题的降阶分支限界算法

作     者：宁爱兵 刘艳芳 支志兵 杨晓芳 NING Ai-bing;LIU Yan-fang;ZHI Zhi-bing;YANG Xiao-fang

作者机构：上海理工大学管理学院上海200093 

基　　金：国家自然科学基金项目(51008196)资助 上海市一流学科项目(XTKX2012)资助 

出 版 物：《小型微型计算机系统》 (Journal of Chinese Computer Systems)

年 卷 期：2014年第35卷第5期

页      码：1124-1127页

摘      要：瓶颈Steiner树问题是经典的组合优化问题,是一个NP难题,在生物网络、交通运输网络、电路设计以及计算机网络布局等领域内有着广泛的应用.本文首先研究瓶颈Steiner树的数学性质,这些数学性质不仅可以判断某些点和边一定在某个最优瓶颈Steiner树中,还可以判断某些点和边一定不在某个最优瓶颈Steiner树中,从而达到降低问题规模和求解难度的目的.然后在瓶颈最小生成树是多项式可解的基础上,提出能快速求解瓶颈Steiner树的降阶分支限界算法.另外文中还通过对多个示例进行分析和求解来阐述算法的原理和过程.

主 题 词：瓶颈Steiner树 瓶颈最小生成树 降阶 分支限界算法 

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

核心收录：

D　O　I：10.3969/j.issn.1000-1220.2014.05.036

馆 藏 号：203643142...