msp问题np完全性研究

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