计算机科学 ›› 2015, Vol. 42 ›› Issue (7): 12-14.doi: 10.11896/j.issn.1002-137X.2015.07.003
吴添君 姜新文
WU Tian-jun JIANG Xin-wen
摘要: 针对文献[1,2]提出的MSP问题,研究了MSP问题与着色问题、子图同构问题的对应关系,揭示了MSP问题所反映的NP完全问题的共性;分析了MSP问题的相变现象,为文献[1,2]提出的多项式时间算法框架的测试提供了难例产生方法。
[1] Jiang Xin-wen.A Polynomial Time Algorithm for the Hamilton Circuit Problem[J].ArXiv preprint cs/1305.5976,2013 [2] Jiang Xin-wen,Peng Li-hong,Wang Qi.MSP Problem:Its NP-completeness and Its Algorithm[C]∥Proceedings of CUTE.2010:1-5 [3] Jiang Xin-wen,Liu Wan-wei,Wu Tian-jun,et al.Reductionsfrom MSP to SAT and from SUBSET SUM to MSP[J].Journal of Computational Information Systems,2014,10(3):1287-1295 [4] Fan Shuo,Jiang Xin-wen.Proving NP-completeness of Polynomial Reduction from the SAT Problem to the MSP Problem (English Abstract)[J].Computer Science,2012,39(11):179-182 [5] Wang Shao-wen.The Study of the Number of Colors on the Graph (English Abstract)[J].Journal of Beijing Institute of Machinery,1997,12(1):15-20 [6] Dong An-guo,Gao Lin,Zhao Jian-bang.Algorithms for Sub-graph Isomorphism in Graph Pattern Mining (English Abstract)[J].Mathematics in Practice and Theory,2011,41(13):105-112 [7] Gebauer H,Szabo T,Tardos G.The Local Lemma Is Tight for SAT[C]∥Proceedings of SODA.2011:664-674 |
No related articles found! |
|