Abstract | ||
---|---|---|
In this paper, we propose a new decision problem, called the concurrently enabled transition set problem, which is proved to be NP-complete by reduction from the independent set problem. Then, we present a polynomial-time algorithm for the maximal concurrently enabled transition set problem, and prove that some special subproblems are in P by the proposed algorithm. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1007/978-3-540-72504-6_20 | TAMC |
Keywords | Field | DocType |
maximal concurrently,special subproblems,independent set problem,computation complexity,new decision problem,transition set problem,polynomial-time algorithm,proposed algorithm,independent set,decision problem,computational complexity | Discrete mathematics,Computational problem,Computer science,Algorithm,P-complete,P versus NP problem,Set packing,Cutting stock problem,Function problem,Vertex cover,Search problem | Conference |
Volume | ISSN | Citations |
4484 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 13 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Pan Li | 1 | 35 | 2.88 |
Weidong Zhao | 2 | 25 | 3.05 |
Zhicheng Wang | 3 | 176 | 17.00 |
Gang Wei | 4 | 0 | 0.68 |
Shumei Wang | 5 | 0 | 0.34 |