OPTIMUM COMMUNICATION SPANNING-TREES IN SERIES-PARALLEL NETWORKS

作     者：ELMALLAH, ES COLBOURN, CJ 

作者机构：UNIV WATERLOODEPT COMP SCIWATERLOO N2L 3G1ONTARIOCANADA 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：1985年第14卷第4期

页      面：915-925页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：spanning tree network design series-parallel graph 2-tree 

摘      要：The optimum communication spanning tree problem is to locate a spanning tree which minimizes the sum of the lengths of the shortest routes between all pairs of vertices in a graph, weighted by traffic requirements. Although NP-complete in general, this problem has an efficient solution for series-parallel graphs when all requirements are equal. This problem was introduced by Hu, who gave an efficient solution for the restricted case when the network is complete and the distances are equal.