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