An Improved Program for the Full Steiner Tree Problem

作     者：Boyce, William M. 

作者机构：Bell Laboratories Murray Hill NJ 07974 600 Mountain Ave. United States 

出 版 物：《ACM Transactions on Mathematical Software (TOMS)》 (ACM Trans. Math. Softw.)

年 卷 期：1977年第3卷第4期

页      面：359-385页

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

主　　题：graph theory minimal networks Steiner trees 

摘      要：A network of minimum total length which connects a given finite planar set A is a union of special trees called full Steiner minimal trees (FSMT), each of which is necessarily also a minimum full Steiner tree (MFST). Extending the earlier work of E.J. Cockayne, we consider the problem of computationally establishing whether there exists an MFST for a given planar set, and if so, exhibiting one. In addition to clarifying the distinction between FSMTs and MFSTs, we are able to revise the computational algorithm so as to speed up Cockayne s program by over an order of magnitude. © 1977, ACM. All rights reserved.