Z-H算法正确性证明第四次改写

• 作者: 姜子恒 姜新文 王琪
• 来源期刊: 计算技术与自动化
• 关键词: 算法 MSP问题 HC问题 NP问题 NP完全问题
• 年，卷（期）: 2010,（3）
• 页码范围: 35-48
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1003-6199.2010.03.009

摘要

提出多级图简单路径求解问题,我们称之为MSP问题.给出求解该问题的Z-H算法,证明算法的正确性,分析算法的时间复杂性.最后通过将HC问题(哈密顿图判定问题)多项式归结成MSP问题,证明MSP问题的NP完全性质.本文极大地简化文献[6,7]中αβ引理的证明,特别是对证明过程中的各种情形进行分割,将一个巨大的证明分成系列引理.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	姜新文	国防科技大学计算机学院	18	101	6.0	8.0
2	王琪	国防科技大学计算机学院	2	8	2.0	2.0
3	姜子恒	国防科技大学计算机学院	2	7	1.0	2.0