Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(3)
Linear Order
npcomplete problem
Polynomial Algorithm
Subscribe
Academic
Publications
MSP Problem: Its NPCompleteness and Its Algorithm
MSP Problem: Its NPCompleteness and Its Algorithm,10.1109/ICUT.2010.5677906,Xinwen Jiang,Lihong Peng,Qi Wang
Edit
MSP Problem: Its NPCompleteness and Its Algorithm
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Xinwen Jiang
,
Lihong Peng
,
Qi Wang
In this paper, we propose a problem named as MSP, prove its NPcompleteness, 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 socalled splitting transform to get a smaller graph. Using the linear order, we prove the nonexistence 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.
Conference:
International Conference on Ubiquitous Information Technologies and Applications  ICUT
, pp. 15, 2010
DOI:
10.1109/ICUT.2010.5677906
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.
(
ieeexplore.ieee.org
)
(
ieeexplore.ieee.org
)
Citation Context
(1)
...This paper is the summarization of [2][3][4][5][6] [
7
][8]...
Xinwen Jiang
,
et al.
MSP Problem: Its NPCompleteness and Its Algorithm
References
(1)
MSP Problem: Its NPCompleteness and Its Algorithm
(
Citations: 1
)
Xinwen Jiang
,
Lihong Peng
,
Qi Wang
Conference:
International Conference on Ubiquitous Information Technologies and Applications  ICUT
, pp. 15, 2010
Sort by:
Citations
(1)
MSP Problem: Its NPCompleteness and Its Algorithm
(
Citations: 1
)
Xinwen Jiang
,
Lihong Peng
,
Qi Wang
Conference:
International Conference on Ubiquitous Information Technologies and Applications  ICUT
, pp. 15, 2010