CMST问题的新算法

• 作 者: 王孔勋 Philip H.Enslow 潘启敬
• 机 构: 美国佐治亚理工学院,西南交通大学计算机科学和工程系Jr.,成都610031
• 出 处: 计算机学报
• 发表日期: 1991年9期
• 关键词: 计算机 网络 树形 拓扑优化 CMST CMST tree network topology optimization.
• 基金项目: 国家自然基金

本文提出了解决按约束条件求最小代价生成树(简称CMST)问题的两个新算法,即给定结点数N,每个结点的负载,链路的代价及链路的容量后,在符合某些约束条件下,求代价最小的树结构.两个新算法的计算复杂性均为O(N~2).计算结果表明,新算法所得结果的代价低于几个现有算法,而计算复杂性比现有算法小得多.