MSP问题NP完全性研究

• 作者: 吴添君 姜新文
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: MSP问题 NP完全 问题归结 相变
• 年，卷（期）: 2015,（7）
• 页码范围: 12-14,27
• 页数: 4页
• 分类号: TP301.5
• 字数: 4201字
• 语种: 中文
• DOI: 10.11896/j.issn.1002-137X.2015.7.003

摘要

针对文献[1,2]提出的MSP问题,研究了MSP问题与着色问题、子图同构问题的对应关系,揭示了MSP问题所反映的NP完全问题的共性;分析了MSP问题的相变现象,为文献[1,2]提出的多项式时间算法框架的测试提供了难例产生方法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	姜新文	国防科技大学计算机学院	18	101	6.0	8.0
2	吴添君	国防科技大学计算机学院	2	7	2.0	2.0