|
|||||
|
|
| 已知拓扑下的4度Steiner树算法 | |
| 引用本文： | 叶继昌,徐寅峰.已知拓扑下的4度Steiner树算法[J].西安交通大学学报,1999,33(6):90-93. |
| 作者姓名： | 叶继昌 徐寅峰 |
| 作者单位： | 西安交通大学,710049,西安 |
| 摘 要： | 设Ｎ为平面上２ｎ个固定点的集合，Ｍ为ｎ－２个可动点的集合，Ｅ为连接这些点的边的集合（也称作拓扑）．设Ｅ为点集Ｖ上的满４度Ｓｔｅｉｎｅｒ拓扑（满Ｓｔｅｉｎｅｒ拓扑也就是满足固定点的度为１，可动点的度为４的树的拓扑），Ｈ（Ｅ）为包含Ｅ在内的所有Ｅ的退化拓扑的集合．文中构造了计算拓扑属于Ｈ（Ｅ）的４度Ｓｔｅｉｎｅｒ树算法，并证明了算法的时间复杂性是Ｏ（ｎ２）． |
| 关 键 词： | Steiner树 拓扑 网络 |
| 修稿时间： | 1998-06-23 |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |