论文部分内容阅读
本文提出了一个计算机网络通信和分布式系统中的一类扩展的Ｓｔｅｉｎｅｒ树问题．对此问题设计了两个求其最优解的算法．这两个算法的时间复杂性分别是Ｏ（３（ｋ－１）·ｎ＋２（ｋ－１）·ｎ２）和Ｏ（２（ｎ－ｋ）·ｎ２）．其中，ｋ是一棵Ｓｔｅｉｎｅｒ树需支撑的给定顶点的个数．
This paper presents a class of extended Steiner tree problem in computer network communication and distributed system. Two algorithms for finding the optimal solution to this problem are designed. The time complexity of these two algorithms is O (3 (k-1) · n + 2 (k-1) · n2) and O (2 (n-k) · n2), respectively. Where k is the number of vertices a Steiner tree needs to support.