| Pendants-median支撑树及其一个相关问题:复杂性和算法 |
| |
| 引用本文： | 付铅生,李帮义. Pendants-median支撑树及其一个相关问题:复杂性和算法[J]. 高等学校计算数学学报, 2004, 26(2): 132-138 |
| |
| 作者姓名： | 付铅生 李帮义 |
| |
| 作者单位： | 南京航空航天大学经济管理学院工商管理系,南京 210016 |
| |
| 基金项目： | 江苏省教育厅人文社科基金(02S5D630020) |
| |
| 摘 要： | The complexity status of Pendants-median spanning tree problem is an open problem. Using the complexity of the X3C problem, the paper proves that Pendants-median spanning tree problem is NP-complete. Global-median spanning tree problem is a related problem. Using the complexity of 3SAT, the paper proves that this problem is also NP-complete, and a polynomial -time algorithm to this problem is given, whose time complexity is O(n^3).
|
| 关 键 词： | 支撑树 集合 NP-完全 最短路树 树叶 |
PENDANTS-MEDIAN SPANNING TREE PROBLEM AND ONE RELATED PROBLEM:COMPLEXITY AND ALGORITHM |
| |
| Fu Qiansheng Li Bangyi. PENDANTS-MEDIAN SPANNING TREE PROBLEM AND ONE RELATED PROBLEM:COMPLEXITY AND ALGORITHM[J]. Numerical Mathematics A Journal of Chinese Universities, 2004, 26(2): 132-138 |
| |
| Authors: | Fu Qiansheng Li Bangyi |
| |
| Abstract: | The complexity status of Pendants-median spanning tree problem is an open problem. Using the complexity of the X3C problem, the paper proves that Pendants-median spanning tree problem is NP-complete. Global-median spanning tree problem is a related problem. Using the complexity of 3SAT, the paper proves that this problem is also NP-complete, and a polynomial -time algorithm to this problem is given, whose time complexity is O(n3). |
| |
| Keywords: | spanning tree NP-complete algorithm. |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
