Pages that link to "Item:Q2570127"
From MaRDI portal
The following pages link to PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation (Q2570127):
Displaying 50 items.
- \textsc{Pull} and \textsc{PushPull} are PSPACE-complete (Q266272) (← links)
- Reconfiguration of dominating sets (Q346508) (← links)
- The complexity of rerouting shortest paths (Q392173) (← links)
- Complexity of independent set reconfigurability problems (Q441866) (← links)
- Approximability of the subset sum reconfiguration problem (Q489711) (← links)
- The kissing problem: how to end a gathering when everyone kisses everyone else goodbye (Q489765) (← links)
- Linear-time algorithm for sliding tokens on trees (Q496016) (← links)
- The complexity of dominating set reconfiguration (Q517018) (← links)
- \textsc{Snowman} is \(\mathsf{PSPACE}\)-complete (Q526872) (← links)
- On the parameterized complexity of reconfiguration problems (Q527426) (← links)
- On the complexity of reconfiguration problems (Q631762) (← links)
- Reconfiguration of list edge-colorings in a graph (Q713316) (← links)
- Shortest paths between shortest paths (Q719258) (← links)
- Generalized Pete's Pike is PSPACE-complete (Q899314) (← links)
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances (Q1034528) (← links)
- Pushing blocks is hard. (Q1395573) (← links)
- The complexity of Snake and undirected NCL variants (Q1623271) (← links)
- Reconfiguration on nowhere dense graph classes (Q1658772) (← links)
- Reconfiguration graphs of shortest paths (Q1660288) (← links)
- Reconfiguration in bounded bandwidth and tree-depth (Q1686224) (← links)
- On the transformation capability of feasible mechanisms for programmable matter (Q1741488) (← links)
- Ice sliding games (Q1791286) (← links)
- Independent-set reconfiguration thresholds of hereditary graph classes (Q1801058) (← links)
- SOKOBAN and other motion planning problems (Q1818116) (← links)
- On girth and the parameterized complexity of token sliding and Token Jumping (Q1979464) (← links)
- Dominating sets reconfiguration under token sliding (Q2032965) (← links)
- Token sliding on split graphs (Q2048202) (← links)
- On reconfigurability of target sets (Q2110378) (← links)
- TS-reconfiguration of dominating sets in circle and circular-arc graphs (Q2140491) (← links)
- Invitation to combinatorial reconfiguration (Q2154076) (← links)
- Traversability, reconfiguration, and reachability in the gadget framework (Q2154080) (← links)
- Pushing lines helps: efficient universal centralised transformations for programmable matter (Q2182711) (← links)
- Parameterized complexity of independent set reconfiguration problems (Q2192091) (← links)
- Reconfiguration of list \(L(2,1)\)-labelings in a graph (Q2250462) (← links)
- Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles (Q2279287) (← links)
- Introduction to reconfiguration (Q2331456) (← links)
- Lemmings is PSPACE-complete (Q2347006) (← links)
- Rerouting shortest paths in planar graphs (Q2403796) (← links)
- Reconfiguration of colorable sets in classes of perfect graphs (Q2632018) (← links)
- Complexity of Hamiltonian cycle reconfiguration (Q2633261) (← links)
- Shortest reconfiguration of sliding tokens on subclasses of interval graphs (Q2658043) (← links)
- Computational complexity of jumping block puzzles (Q2695336) (← links)
- Reconfiguration of cliques in a graph (Q2700609) (← links)
- Shortest Reconfiguration of Sliding Tokens on a Caterpillar (Q2803826) (← links)
- Independent set reconfiguration in cographs and their generalizations (Q2825488) (← links)
- Vertex Cover Reconfiguration and Beyond (Q2942651) (← links)
- Reconfiguration of Vertex Covers in a Graph (Q2946052) (← links)
- PSPACE-Completeness of Bloxorz and of Games with 2-Buttons (Q2947039) (← links)
- The Complexity of (List) Edge-Coloring Reconfiguration Problem (Q2980922) (← links)
- Sliding Tokens on Block Graphs (Q2980933) (← links)
