A Practical Algorithm for the Minimum RectilinearSteiner Tree

作     者：马军 杨波 马绍汉 

作者机构：Department of Computer Science Shandong University Jinan P.R. China 

出 版 物：《Journal of Computer Science & Technology》 (计算机科学技术学报（英文版）)

年 卷 期：2000年第15卷第1期

页      面：96-99页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0835[工学-软件工程] 0701[理学-数学] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

基　　金：国家自然科学基金 国家863计划 

主　　题：Steiner tree complexity theory combination optimization 

摘      要：An O(n2) time approximation algorithm for the minimum rectilinear Steiner tree is proposed. The approximation ratio of the algorithm is strictlyless than 1.5. The computing performances show the costs of the spanning treesproduced by the algorithm are only 0.8% away from the optimal ones.