On the Complexity of Reconfiguration Problems

被引：0

作者：

Ito, Takehiro ^{[1
]}

Demaine, Erik D. ^{[2
]}

Harvey, Nicholas J. A. ^{[3
]}

Papadimitriou, Christos H. ^{[4
]}

Sideri, Martha ^{[5
]}

Uehara, Ryuhei ^{[6
]}

Uno, Yushi ^{[7
]}

机构：

[1] Tohoku Univ, Grad Sch Informat Sci, Aoba Yama 6-6-05, Sendai, Miyagi 9808579, Japan

[2] MIT Comp Sci & Artificial Intelligence Lab, Cambridge, MA 02139 USA

[3] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON 2L3G1, Canada

[4] Univ Calif Berkeley, Div Comp Sci, Berkeley, CA 94720 USA

[5] Athens Univ Econ & Business, Dept Comp Sci, Athens 10434, Greece

[6] JAIST, Sch Informat Sci, Nomi 9231292, Japan

[7] Osaka Prefecture Univ, Grad Sch Sci, Sakai, Osaka 5998531, Japan

来源：

ALGORITHMS AND COMPUTATION, PROCEEDINGS | 2008年 / 5369卷

关键词：

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 A A 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.

引用

页码：28 / +

页数：2

共 15 条

[1]

Bonsma P, 2007, LECT NOTES COMPUT SC, V4708, P738

[2]

Cook W.J., 1997, Combinatorial optimization

[3]

Edmonds J., 1971, Math. Program, V1, P127, DOI [DOI 10.1007/BF01584082, 10.1007/BF01584082]

[4] A threshold of in n for approximating set cover [J].