Grid graphs with diagonal edges and the complexity of Xmas mazes
Holzer, Markus ;
Jakobi, Sebastian
Zum Volltext im pdf-Format:
Dokument 1.pdf (229 KB)
Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-90834
URL: http://geb.uni-giessen.de/geb/volltexte/2012/9083/
Freie Schlagwörter (Englisch):
constraint logic , grid graph reachability , puzzles
Universität
Justus-Liebig-Universität Gießen
Institut:
Institut für Informatik
Fachgebiet:
Informatik
DDC-Sachgruppe:
Informatik
Dokumentart:
ResearchPaper
Zeitschrift, Serie:
IFIG Research Report
; 1201 / 2012
Sprache:
Englisch
Erstellungsjahr:
2012
Publikationsdatum:
23.11.2012
Kurzfassung auf Deutsch:
We investigate the computational complexity of some maze problems, namely the reachability problem for (undirected) grid graphs with diagonal edges, and the solvability of Xmas tree mazes. Simply speaking, in the latter game one has to move sticks of a certain length through a maze, ending in a particular game situation. It turns out that when the number of sticks is bounded by some constant, these problems are closely related to the grid graph problems with diagonals. If on the other hand an unbounded number of sticks is allowed, then the problem of solving such a maze becomes PSPACE-complete. Hardness is shown via a reduction from the nondeterministic constraint logic (NCL) of Demaine and Hearn to Xmas tree mazes.
Lizenz:
Veröffentlichungsvertrag für Publikationen ohne Print on Demand
