Show simple item record

dc.contributor.authorHolzer, Markus
dc.contributor.authorJakobi, Sebastian
dc.date.accessioned2022-09-12T09:38:49Z
dc.date.available2012-11-23T10:01:15Z
dc.date.available2022-09-12T09:38:49Z
dc.date.issued2012
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:hebis:26-opus-90834
dc.identifier.urihttps://jlupub.ub.uni-giessen.de//handle/jlupub/7580
dc.identifier.urihttp://dx.doi.org/10.22029/jlupub-7014
dc.description.abstractWe 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.de_DE
dc.language.isoende_DE
dc.relation.ispartofseriesIFIG Research Report; 1201 / 2012
dc.rightsIn Copyright*
dc.rights.urihttp://rightsstatements.org/page/InC/1.0/*
dc.subjectconstraint logicen
dc.subjectgrid graph reachabilityen
dc.subjectpuzzlesen
dc.subject.ddcddc:004de_DE
dc.titleGrid graphs with diagonal edges and the complexity of Xmas mazesde_DE
dc.typeworkingPaperde_DE
local.affiliationFB 07 - Mathematik und Informatik, Physik, Geographiede_DE
local.opus.id9083
local.opus.instituteInstitut für Informatikde_DE
local.opus.fachgebietInformatikde_DE


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

In Copyright