Traversability, reconfiguration, and reachability in the gadget framework

DOI10.1007/s00453-023-01140-0MaRDI QIDQ6090541

Erik D. Demaine, Jayson Lynch, Joshua Ani, Dylan Hendrickson, Yevhenii Diomidov

Publication date: 17 November 2023

Published in: Algorithmica (Search for Journal in Brave)

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• PSPACE-completeness of reversible deterministic systems
• Traversability, reconfiguration, and reachability in the gadget framework
• Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets
• Relationships between nondeterministic and deterministic tape complexities
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Nondeterministic Space is Closed under Complementation
• The Planar Hamiltonian Circuit Problem is NP-Complete
• On the complexity of edge traversing
• The complexity of graph connectivity
• Full Tilt: Universal Constructors for General Shapes with Uniform External Forces
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Traversability, reconfiguration, and reachability in the gadget framework