The complexity of Snake and undirected NCL variants
DOI10.1016/J.TCS.2017.10.031zbMATH Open1402.68088OpenAlexW2767722150MaRDI QIDQ1623271FDOQ1623271
Authors: Marzio De Biasi, Tim Ophelders 
Publication date: 23 November 2018
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://research.tue.nl/nl/publications/the-complexity-of-snake-and-undirected-ncl-variants(110a6b03-3609-4787-a566-656d6f52f5b6).html
Recommendations
- The Complexity of Snake
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- scientific article; zbMATH DE number 2086639
- The parameterized complexity of motion planning for snake-like robots
- Gaming is a hard job, but someone has to do it!
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43)
Cites Work
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- On Embedding a Graph in the Grid with the Minimum Number of Bends
- Games, puzzles, and computation
- Playing games with algorithms: algorithmic combinatorial game theory
- On two geometric problems related to the travelling salesman problem
- The train marshalling problem
- Gaming is a hard job, but someone has to do it!
- Parameterized complexity of graph constraint logic
- Simple wriggling is hard unless you are a fat hippo
Cited In (4)
This page was built for publication: The complexity of Snake and undirected NCL variants
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1623271)
