MSP问题及其求解研究

摘要：

本文提出了多级图简单路径求解问题,我们称之为MSP问题.给出求解该问题的Z-H算法,证明算法的正确性,分析算法的时间复杂性.最后通过将HC问题(哈密顿图判定问题)多项式归结成MSP问题,证明MSP问题的NP完全性质.结论是:MSP∈P,HC∈P.

关键词： MSP问题 HC问题 NP问题 NP完全问题

作者: 姜新文

作者单位: 国防科技大学,计算机学院,湖南,长沙,410073

会议类型: 国内会议

会议名称: 中南六省(区)自动化学会第24届学术年会

会议地点: 南宁

会议语种:中文

页码: 145-159

在线出版日期: 2006-11-01（万方平台首次上网日期，不代表论文的发表时间）