| 次最小树及其相关问题-算法设计和复杂性分析 |
| |
| 引用本文： | 李帮义.次最小树及其相关问题-算法设计和复杂性分析[J].高等学校计算数学学报,2002,24(3):283-288. |
| |
| 作者姓名： | 李帮义 |
| |
| 作者单位： | 南京航空航天大学经济管理学院,南京,210016 |
| |
| 基金项目： | 国家自然科学基金（70171028），南航青年基金（S0133—092）. |
| |
| 摘 要： | 支撑树问题已经有很长的研究历史了,见1].在许多工程问题中,需要产生一个网络G的所有支撑树,见2,3,4].当G为赋权图时,每棵支撑树T有长度L（T）.在产生G的所有支撑树时,许多工程问题希望按照L（T）的非降顺序产生,见5,6].在按照L（T）的非降顺序产生的支撑树中,有许多支撑树长度是相同的,而支撑树的数目又非常大（可以高达nn-2个）,因此算法的计算量非常大.本文希望能够按照L（T）的严格上升顺序产生所有的支撑树,从而避免大量的重复计算.
|
| 关 键 词： | 次最小树 算法设计 复杂性 |
| 修稿时间： | 2001年6月26日 |
THE SECOND-MINIMUM SPANNING TREES AND RELATED PROBLEMS-ALGORITHM DESIGN AND COMPLEXITY |
| |
| Li Bangyi.THE SECOND-MINIMUM SPANNING TREES AND RELATED PROBLEMS-ALGORITHM DESIGN AND COMPLEXITY[J].Numerical Mathematics A Journal of Chinese Universities,2002,24(3):283-288. |
| |
| Authors: | Li Bangyi |
| |
| Abstract: | This paper puts forward the concept of kth minimum spanning trees. For the special case k = 2, an polynomial algorithm is given, whose time complexity is O(mn), where m is the number of edges in the network, n is the number of vertices. By using the fixed length spanning tree problem, it proves that finding the spanning tree length distributions problem is NP-C. |
| |
| Keywords: | kth mimimum spanning trees algorithm time complexity NP-C |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
