MSP Problem: Its NP-Completeness and Its Algorithm

MSP Problem: Its NP-Completeness and Its Algorithm,10.1109/ICUT.2010.5677906,Xinwen Jiang,Lihong Peng,Qi Wang

MSP Problem: Its NP-Completeness and Its Algorithm   (Citations: 1)
BibTex | RIS | RefWorks Download
In this paper, we propose a problem named as MSP, prove its NP-completeness, and design an algorithm to solve it. To prove the algorithm, we define a linear order to align all the instances of the problem, and also define a so-called splitting transform to get a smaller graph. Using the linear order, we prove the non-existence of the smallest graph which makes our algorithm failed by performing splitting transform on the smallest graph to obtain a smaller graph. It seems that our algorithm is a polynomial one. So we would like to discuss it with more people. This paper is the summarization of.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: