MSP问题及其求解研究

• 作者: 姜新文
• 来源期刊: 计算技术与自动化
• 关键词: 算法 MSP问题 HC问题 NP问题 NP完全问题
• 年，卷（期）: 2006,（4）
• 所属期刊栏目: 算法分析与研究
• 页码范围: 145-159
• 页数: 15页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1003-6199.2006.04.039

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	姜新文	国防科技大学计算机学院	18	101	6.0	8.0