| Z-H算法正确性证明第四次改写 |
 点此下载全文 |
| 引用本文：姜新文,王琪,姜子恒.Z-H算法正确性证明第四次改写[J].计算技术与自动化,2010,(3):35-48 |
| 摘要点击次数: 2375 |
| 全文下载次数: 274 |
|
|
| 中文摘要:提出多级图简单路径求解问题，我们称之为MSP问题。给出求解该问题的Z-H算法，证明算法的正确性，分析算法的时间复杂性。最后通过将HC问题（哈密顿图判定问题）多项式归结成MSP问题，证明MSP问题的NP完全性质。本文极大地简化文献［6，7］中αβ引理的证明，特别是对证明过程中的各种情形进行分割，将一个巨大的证明分成系列引理。 |
| 中文关键词:算法 MSP问题 HC问题 NP问题 NP完全问题 |
| |
| The Fourth Version of The Proof for Z-H Algorithm to Solve MSP Problem |
|
|
| Abstract:It is introduced a new problem to be named as MSP and an algorithm to solve MSP in this paper. The time complexity of the algorithm is a polynomial function of |V|*|E|, where, |V| stands for the number of vertex and |E| stands for the number of edges of the given graph.The contribution of the new proof is that we divide the giant proof in ［6,7］ into several parts so that people can be easier to grasp. |
| keywords:algorithm MSP problem HC problem NP problem NP –complete prolem |
| 查看全文 查看/发表评论 下载pdf阅读器 |
位访问者,今日访问
次