基于CBT的多源Steiner树构造算法

• 作者: 刘捷 周俊懿 马金柱
• 来源期刊: 计算机工程与设计
• 学科: 工学
• 关键词: Steiner树 多播 链路共享 共享路径 启发式算法 核心树
• 年，卷（期）: 2006,（17）
• 所属期刊栏目: 基金项目论文
• 页码范围: 3172-3174
• 页数: 3页
• 分类号: TP393.02
• 字数: 3359字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-7024.2006.17.020

摘要

构造最小代价树问题可形式化为图论中Steiner树问题.而Steiner树的求解已经被证明是一个NP-complete问题,不可能在多项式时间求得其精确解,所以出现许多启发式算法:在可接受时间内,得到一棵近似的最优多播树.这些算法一般沣先指定所有链接边的费用,通过一定方法或规则,找出包含源端和所有目的端的一棵近似最优的多播树.很显然,它们并没有考虑由于路径的共享重叠而引起最小生成树链接边费用的变化.现利用CBT算法思想对变化的费用进行建模并对典型启发式算法作了改进,以适应不断变化了的链路费用.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘捷	山东大学计算机科学与技术学院	14	101	5.0	10.0
2	周俊懿	山东大学计算机科学与技术学院	2	7	2.0	2.0
3	马金柱	山东大学计算机科学与技术学院	2	4	1.0	2.0