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”, in Proceedings of the 19th Annual International Symposium on Algorithms and Computation (ISAAC 2008), Gold Coast, Australia, December 15–17, 2008, pages 28–39.
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 SpringerLink.
- The paper is 12 pages.
- The paper is available in PostScript (1134k) and PDF (176k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- NPReconfiguration_TCS (On the Complexity of Reconfiguration Problems)
- NPReconfiguration_WADS2009 (Reconfiguration of List Edge-Colorings in a Graph)
- SubsetSumReconfiguration_JOCO (Approximability of the Subset Sum Reconfiguration Problem)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated June 7, 2021 by