On the Complexity of Reconfiguration Problems

DOI10.1007/978-3-540-92182-0_6MaRDI QIDQ3596704zbMATH OpenOpenAlexFDO

Authors Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Ryuhei Uehara, Yushi Uno, Christos Papadimitriou, Martha Sideri

Publication date 29 January 2009

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-92182-0_6

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the complexity of reconfiguration problems
• Introduction to reconfiguration

Cited in

(21)

• Reconfiguration in bounded bandwidth and tree-depth
• Editorial: Special issue on reconfiguration problems
• Difficult configurations -- on the complexity of LTrL
• On reconfigurability of target sets
• On the complexity of optimal matching reconfiguration
• On the polynomiality of finding \(^K\text{DMDGP}\) re-orders
• Introduction to reconfiguration
• Inferring local transition functions of discrete dynamical systems from observations of system behavior
• Minimum maximum reconfiguration cost problem
• The complexity of change
• On the Complexity of Reconfiguration in Systems with Legacy Components
• Degree-constrained subgraph reconfiguration is in P
• Shortest Paths between Shortest Paths and Independent Sets
• Reconfiguration of List Edge-Colorings in a Graph
• The complexity of rerouting shortest paths
• On limitations of transformations between combinatorial problems
• Congestion-free rerouting of flows on DAGs
• Reconfiguration of graph minors
• On the complexity of reconfiguration problems
• Hamiltonian cycle reconfiguration with answer set programming
• Shortest paths between shortest paths

This page was built for publication: On the Complexity of Reconfiguration Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3596704)