The complexity of Snake and undirected NCL variants

DOI10.1016/j.tcs.2017.10.031zbMath1402.68088OpenAlexW2767722150MaRDI QIDQ1623271

Tim Ophelders, Marzio De Biasi

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

zbMATH Keywords

puzzlesmotion planninggamesnondeterministic constraint logicPSPACE

Mathematics Subject Classification ID

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

Related Items (4)

Reconfiguring (non-spanning) arborescences ⋮ Reconfiguration of time-respecting arborescences ⋮ Reconfiguring directed trees in a digraph ⋮ The Parameterized Complexity of Motion Planning for Snake-Like Robots

Cites Work

• Unnamed Item
• Gaming is a hard job, but someone has to do it!
• Simple wriggling is hard unless you are a fat hippo
• The train marshalling problem
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• On two geometric problems related to the travelling salesman problem
• Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• Parameterized Complexity of Graph Constraint Logic

This page was built for publication: The complexity of Snake and undirected NCL variants