Name
Abstract | ||
|---|---|---|
Reconfiguration problems arise when we wish to find a step-by-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. We demonstrate that a host of reconfiguration problems derived from NP-complete problems are PSPACE-complete, while some are also NP-hard to approximate. In contrast, several reconfiguration versions of problems in P are solvable in polynomial time. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.tcs.2010.12.005 | Theoretical Computer Science |
Keywords | DocType | Volume |
step-by-step transformation,graph algorithm,reconfiguration version,reconfiguration problem,polynomial time,np-complete problem,reachability on solution space,intermediate result,feasible solution,approximation,pspace-complete | Conference | 412 |
Issue | ISSN | Citations |
12-14 | Theoretical Computer Science | 62 |
PageRank | References | Authors |
3.27 | 13 | 7 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Takehiro Ito | 1 | 260 | 40.71 |
| Erik D. Demaine | 2 | 4624 | 388.59 |
| Nicholas J. A. Harvey | 3 | 909 | 57.85 |
| Christos H. Papadimitriou | 4 | 16671 | 3192.54 |
| Martha Sideri | 5 | 409 | 46.17 |
| Ryuhei Uehara | 6 | 528 | 75.38 |
| yushi uno | 7 | 222 | 28.80 |