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

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

Recommendations

• On the complexity of reconfiguration problems
• Introduction to reconfiguration

Cited in

(21)

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

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)