MSP问题的一个求解算法  

A New Algorithm for the MSP Problem

作　　者：姜新文[1] 吴添君 李鹏坤[1] 樊硕[1] 周泰杨 魏登萍[1] 

机构地区：[1]国防科技大学计算机学院,湖南长沙410073

出　　处：《计算技术与自动化》2016年第1期60-70,共11页Computing Technology and Automation

基　　金：国家自然科学基金项目(61272010)

摘　　要：MSP问题是文献[1,2]提出的一个问题。研究表明[3]该问题对NP类问题有很强的表达能力。本文给出一个关于该问题的求解算法、复杂性分析,以及正确性证明。本文对于NP完全问题研究有重要意义。In this paper,we introduce a so-called Multistage graph Simple Path（MSP）problem.Many researches in the past several years have shown that the MSP problem is powerful to express NP problem.To solve the MSP problem,we propose a polynomial algorithm.

关 键 词：算法 MSP问题 算法设计 复杂性 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]