| MSP问题NP完全性研究 |
| |
| 引用本文： | 吴添君,姜新文.MSP问题NP完全性研究[J].计算机科学,2015,42(7):12-14, 27. |
| |
| 作者姓名： | 吴添君 姜新文 |
| |
| 作者单位： | 国防科技大学计算机学院 长沙410073 |
| |
| 基金项目： | 本文受国家自然科学基金(61272010)资助 |
| |
| 摘 要： | 针对文献1,2]提出的MSP问题,研究了MSP问题与着色问题、子图同构问题的对应关系,揭示了MSP问题所反映的NP完全问题的共性；分析了MSP问题的相变现象,为文献1,2]提出的多项式时间算法框架的测试提供了难例产生方法。
|
| 关 键 词： | MSP问题 NP完全 问题归结 相变 |
On NP-completeness of MSP Problem |
| |
| WU Tian-jun JIANG Xin-wen.On NP-completeness of MSP Problem[J].Computer Science,2015,42(7):12-14, 27. |
| |
| Authors: | WU Tian-jun JIANG Xin-wen |
| |
| Affiliation: | College of Computer Science,National University of Defense Technology,Changsha 410073,China |
| |
| Abstract: | 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]. |
| |
| Keywords: | MSP problem NP-complete Problem reduction Phase transition |
|
|
点击此处可从《计算机科学》下载全文 |
|
