| 求解满瓶颈Steiner树 |
| |
| 引用本文： | 康妮妮,唐恒永.求解满瓶颈Steiner树[J].沈阳师范大学学报(自然科学版),2008,26(1):7-9. |
| |
| 作者姓名： | 康妮妮 唐恒永 |
| |
| 作者单位： | 沈阳师范大学,数学与系统科学学院,辽宁,沈阳,110034 |
| |
| 摘 要： | 首先对Steiner树,瓶颈Steiner树研究现状加以介绍,指出满瓶颈Steiner树就是在已知图中找一颗树S,使给定的点集在S中的点都为叶子,且最大的边权值最小,然后给出满瓶颈Steiner树的定义,利用分解,转化,组合的思想,给出求解满瓶颈Steiner树问题的一个多项式算法,证明算法正确性,说明该算法的时间复杂性,最后给出相应的数值例子,说明算法正确性.
|
| 关 键 词： | 满瓶颈Steiner树 最小支撑树 多项式算法 时间复杂性 求解 瓶颈 Steiner Tree Problem Bottleneck 数值例子 时间复杂性 算法正确性 多项式算法 问题 思想 组合 转化 分解 利用 最小 权值 现状 研究 |
| 文章编号： | 1673-5862（2008）01-0007-03 |
| 收稿时间： | 2007-03-10 |
| 修稿时间： | 2007年3月10日 |
On Full Bottleneck Steiner Tree Problem |
| |
| KANG Ni-ni,TANG Heng-yong.On Full Bottleneck Steiner Tree Problem[J].Journal of Shenyang Normal University: Nat Sci Ed,2008,26(1):7-9. |
| |
| Authors: | KANG Ni-ni TANG Heng-yong |
| |
| Abstract: | It is suggested to solve the full bottleneck Steiner tree problem is to find a tree S from the undirected graph G, with all the vertices in the given points being leaves and the weights of the maximum edges being minimum. After giving out the definition of full bottleneck Steiner tree, we use methed of transforming, decomposing and combining to give out a polynominal algorithm for solving the problem. Complexity of time in that algorithm is given, and examples are presented to show the validity of the algorithm. |
| |
| Keywords: | full bottleneck Steiner tree minimum spanning tree polynomial algorithm complexity of time |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
