The complexity of Snake and undirected NCL variants

DOI10.1016/J.TCS.2017.10.031MaRDI QIDQ1623271zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

motion planningnondeterministic constraint logicgamesPSPACEpuzzles

Mathematics Subject Classification ID

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

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!

Cites work

• Games, puzzles, and computation
• Gaming is a hard job, but someone has to do it!
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• On two geometric problems related to the travelling salesman problem
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Parameterized complexity of graph constraint logic
• Playing games with algorithms: algorithmic combinatorial game theory
• Simple wriggling is hard unless you are a fat hippo
• The train marshalling problem

Cited in

(4)

• Reconfiguration of time-respecting arborescences
• The parameterized complexity of motion planning for snake-like robots
• Reconfiguring (non-spanning) arborescences
• Reconfiguring directed trees in a digraph

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)