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

摘要：

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

关键词：Steiner树、多播、链路共享、共享路径、启发式算法、核心树

所属期刊栏目：27

分类号：TP393.02(计算技术、计算机技术)

资助基金：山东省优秀中青年科学家科研奖励基金03BS004

在线出版日期：2006-10-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：3172-3174