欧式平面上瓶颈Steiner树问题的一个近似算法

导出

摘要近些年来，Steiner树问题在理论和应用上都引起了极大的关注，尤其在日渐成熟的近似算法设计理论方面，该问题占有一定的中心地位。给定赋权连通图G=(V，E，W)及顶点子集S包含V(S中顶点称为terminals)，传统的Steiner树问题要求寻找一棵最小的树联接5中的所有顶点，该树可能包含V-S中的顶点(称为Steiner点)。即使图中每条边的权值仅限制为1或2时，传统的Steiner树问题仍然是MAX—SNP Hard。

作者 Zi-MaoLi Da-MingZhu Shao-HanMa

机构地区 SchoolofComputerScienceandTechnology

出处《Journal of Computer Science & Technology》 SCIE EI CSCD 2004年第C00期39-39,共1页 计算机科学技术学报（英文版）

关键词顶点子集近似算法 Steiner点连通图 STEINER树平面赋权 MAX 权值瓶颈

分类号 TP393 [自动化与计算机技术—计算机应用技术] O157.5 [自动化与计算机技术—计算机科学与技术]

引文网络
相关文献

1蒋俊华.p-平行体类及其p-Steiner点的连续性[J].应用数学与计算数学学报,2012,26(2):143-147.
2陈光亭,姚恩瑜.λ5-geometry中的Steiner树问题( )[J].高校应用数学学报（A辑）,2002,17(1):56-62.
3徐永存,梁久祯,王德江.基于Steiner点的移动目标遮挡恢复方法[J].南京大学学报（自然科学版）,2015,51(2):405-414.
4张晗方.E^n空间中Steiner树的性质与极值[J].徐州师范大学学报（自然科学版）,2002,20(1):1-6. 被引量：1
5杨振骏.关于Steiner最短树算法的改进[J].江苏电机工程,1997,16(1):14-18. 被引量：1
6陈光亭,姚恩瑜.带圆周约束的Steiner树问题[J].高校应用数学学报（A辑）,1998,13(4):473-478. 被引量：1
7吴才斌.插值法及其应用[J].当代继续教育,1999,29(5):77-80. 被引量：3
8吴敏.插值与迭代[J].大众科技,2009,11(2):23-24. 被引量：2
9杨洪,张修军,邵泽辉.一种求解最大团问题的化学反应算法[J].成都大学学报（自然科学版）,2017,36(1):43-46.
10宋昭润.求赋权连通图最优树的用边率[J].湘潭大学自然科学学报,1995,17(4):101-105.

Journal of Computer Science & Technology

2004年第C00期

浏览历史

内容加载中请稍等...

欧式平面上瓶颈Steiner树问题的一个近似算法

相关作者

相关机构

相关主题

浏览历史