改进的Steiner树近似算法

摘要：

DNH算法有较好的近似比,所得到Steiner树具有2(1-1/|S|)的性能,但其时间复杂度为O(|S|(|V|log|V|+|E|)).本文将对DNH算法加以改进,使复杂度降为O(|V|log|V|+|E|),并证明了改进算法的性能将保持不变.

关键词： Steiner树 DNH算法 改进算法

作者: 高磊 王晓东

作者单位: 西安交通大学(西安) 福州大学计算机科学与技术系(福州)

会议类型: 国内会议

会议名称: 2001年全国理论计算机科学学术会议

会议地点: 福州

会议语种:中文

页码: 282-284

在线出版日期: 2001-09-01（万方平台首次上网日期，不代表论文的发表时间）