Paper by Erik D. Demaine
- Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno, “On the Complexity of Reconfiguration Problems”, Theoretical Computer Science, volume 412, number 12-14, 2011, pages 1054–1065.
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
- This paper is also available from ScienceDirect.
- The paper is 12 pages.
- The paper is available in PDF (451k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- NPReconfiguration_ISAAC2008 (On the Complexity of Reconfiguration Problems)
- SubsetSumReconfiguration_JOCO (Approximability of the Subset Sum Reconfiguration Problem)
- NPReconfiguration_WADS2009 (Reconfiguration of List Edge-Colorings in a Graph)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated December 15, 2022 by