求解满瓶颈Steiner树

• 作者: 唐恒永 康妮妮
• 来源期刊: 沈阳师范大学学报(自然科学版)
• 学科: 数学
• 关键词: 满瓶颈Steiner树 最小支撑树 多项式算法 时间复杂性
• 年，卷（期）: 2008,（1）
• 页码范围: 7-9
• 页数: 3页
• 分类号: O221.7|O115.7
• 字数: 2344字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-5862.2008.01.002

摘要

首先对Steiner树,瓶颈Steiner树研究现状加以介绍,指出满瓶颈Steiner树就是在已知图中找一颗树S,使给定的点集在S中的点都为叶子,且最大的边权值最小,然后给出满瓶颈Steiner树的定义,利用分解,转化,组合的思想,给出求解满瓶颈Steiner树问题的一个多项式算法,证明算法正确性,说明该算法的时间复杂性,最后给出相应的数值例子,说明算法正确性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	唐恒永	沈阳师范大学数学与系统科学学院	75	433	11.0	16.0
2	康妮妮	沈阳师范大学数学与系统科学学院	2	5	1.0	2.0