-
题名瓶颈Steiner树问题的降阶分支限界算法
- 1
-
-
作者
宁爱兵
刘艳芳
支志兵
杨晓芳
-
机构
上海理工大学管理学院
-
出处
《小型微型计算机系统》
CSCD
北大核心
2014年第5期1124-1127,共4页
-
基金
国家自然科学基金项目(51008196)资助
上海市一流学科项目(XTKX2012)资助
-
文摘
瓶颈Steiner树问题是经典的组合优化问题,是一个NP难题,在生物网络、交通运输网络、电路设计以及计算机网络布局等领域内有着广泛的应用.本文首先研究瓶颈Steiner树的数学性质,这些数学性质不仅可以判断某些点和边一定在某个最优瓶颈Steiner树中,还可以判断某些点和边一定不在某个最优瓶颈Steiner树中,从而达到降低问题规模和求解难度的目的.然后在瓶颈最小生成树是多项式可解的基础上,提出能快速求解瓶颈Steiner树的降阶分支限界算法.另外文中还通过对多个示例进行分析和求解来阐述算法的原理和过程.
-
关键词
瓶颈steiner树
瓶颈最小生成树
降阶
分支限界算法
-
Keywords
bottleneck steiner tree problem
minimum bottleneck spanning tree
reduction
branch and bound algorithm
-
分类号
TP301
[自动化与计算机技术—计算机系统结构]
-
-
题名基于范数下的反瓶颈Steiner树问题
- 2
-
-
作者
吴爽
刘洋
康妮妮
唐恒永
-
机构
沈阳师范大学数学与系统科学学院
-
出处
《沈阳师范大学学报（自然科学版）》
CAS
2009年第1期13-15,共3页
-
基金
国家自然科学基金资助项目(10471096)
-
文摘
讨论了在l1范数下的反瓶颈Steiner树问题.对于给定的一个可行解,修改带限制的边权使其成为瓶颈Steiner树问题的最优解,并且在l1范数下边权的修改费用最小.讨论了最优目标值的范围,在此基础上给出了一个求解反瓶颈Steiner问题的多项式时间算法.
-
关键词
反问题
瓶颈steiner树
L1范数
多项式时间算法
-
Keywords
inverse problem
bottleneck steiner tree
l1 norm
polynomial algorithm
-
分类号
F224.33
[经济管理—国民经济]
-
