Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard
From MaRDI portal
Publication:3088169
DOI10.1007/978-3-642-22670-0_1zbMath1343.68093OpenAlexW196900508MaRDI QIDQ3088169
Publication date: 19 August 2011
Published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22670-0_1
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games on graphs (graph-theoretic aspects) (05C57)
Related Items (11)
Multi-agent Pathfinding with n Agents on Graphs with n Vertices: Combinatorial Classification and Tight Algorithmic Bounds ⋮ Sequentially Swapping Colored Tokens on Graphs ⋮ Token Swapping on Trees ⋮ Reconfiguration of connected graph partitions ⋮ Multi-color pebble motion on graphs ⋮ Sequentially Swapping Colored Tokens on Graphs ⋮ \textsc{Snowman} is \(\mathsf{PSPACE}\)-complete ⋮ Feasibility of motion planning on acyclic and strongly connected directed graphs ⋮ On reachability in graphs with obstacles ⋮ Proximity Oblivious Testing and the Role of Invariances ⋮ Introduction to reconfiguration
Cites Work
This page was built for publication: Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard
