| MSP问题及其求解研究 |
| |
| 引用本文： | 姜新文. MSP问题及其求解研究[J]. 计算技术与自动化, 2006, 25(4): 145-159 |
| |
| 作者姓名： | 姜新文 |
| |
| 作者单位： | 国防科技大学,计算机学院,湖南,长沙,410073 |
| |
| 摘 要： | 提出多级图简单路径求解问题,我们称之为MSP问题.给出求解该问题的Z-H算法,证明算法的正确性,分析算法的时间复杂性.最后通过将HC问题(哈密顿图判定问题)多项式归结成MSP问题,证明MSP问题的NP完全性质.结论是MSP∈P,HC∈P.
|
| 关 键 词： | 算法 MSP问题 HC问题 NP问题 NP完全问题 |
| 文章编号： | 1003-6199(2006)04-0145-15 |
| 修稿时间： | 2006-08-18 |
MSP Problem:Its NP-Completeness and Its Algorithm |
| |
| JIANG Xin-wen. MSP Problem:Its NP-Completeness and Its Algorithm[J]. Computing Technology and Automation, 2006, 25(4): 145-159 |
| |
| Authors: | JIANG Xin-wen |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
|
