MSP问题NP完全性研究  

On NP-completeness of MSP Problem

作　　者：吴添君 姜新文[1] 

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

出　　处：《计算机科学》2015年第7期12-14,27,共4页Computer Science

基　　金：国家自然科学基金(61272010)资助

摘　　要：针对文献[1,2]提出的MSP问题,研究了MSP问题与着色问题、子图同构问题的对应关系,揭示了MSP问题所反映的NP完全问题的共性;分析了MSP问题的相变现象,为文献[1,2]提出的多项式时间算法框架的测试提供了难例产生方法。Based on the MSP（multistage graph simple path）problem in [1,2],we studied the correlation between MSP,K-Coloring and sub-graph isomorphism,revealed the expressive property of MSP to better understand NP-completeness,and analyzed the phase-transition phenomenon of the MSP problem in order to generate hard test cases for the relevant polynomial-time algorithm proposed in[1,2].

关 键 词：MSP问题 NP完全 问题归结 相变 

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