| 一类扩展的Steiner树优化问题及其应用 |
| |
| 引用本文： | 梁东敏,马绍汉.一类扩展的Steiner树优化问题及其应用[J].计算机学报,1996(12). |
| |
| 作者姓名： | 梁东敏 马绍汉 |
| |
| 作者单位： | 山东大学计算机科学系 |
| |
| 摘 要： | 本文提出了一个计算机网络通信和分布式系统中的一类扩展的Ｓｔｅｉｎｅｒ树问题．对此问题设计了两个求其最优解的算法．这两个算法的时间复杂性分别是Ｏ（３（ｋ－１）·ｎ＋２（ｋ－１）·ｎ２）和Ｏ（２（ｎ－ｋ）·ｎ２）．其中，ｋ是一棵Ｓｔｅｉｎｅｒ树需支撑的给定顶点的个数．
|
| 关 键 词： | 图算法，Steiner树，复杂性 |
AN EXTENDED STEINER TREE OPTIMIZATION PROBLEM AND ITS APPLICATIONS |
| |
| Liang Dongmin and Ma Shaohan.AN EXTENDED STEINER TREE OPTIMIZATION PROBLEM AND ITS APPLICATIONS[J].Chinese Journal of Computers,1996(12). |
| |
| Authors: | Liang Dongmin and Ma Shaohan |
| |
| Abstract: | In this paper, a Steiner tree problem in computer networks and distributed systems is defined. Two algorithms are proposed to solve the problem.Both can find an optimal solution and run in O(3k-1. n+2k-1. n2) and O(2n-k. n2)time,reflectively,where k is the number of the given venices that the Steiner tree spans. |
| |
| Keywords: | Graph algorithms Steiner tree complexity |
| 本文献已被 CNKI 等数据库收录！ |
