Repozytorium publikacji - Politechnika Gdańska

Rozważamy następującą grę (pomiędzy dwoma graczami) kombinatoryczną o nazwie ''node blocking''. Dany jest graf skierowany. Każdy wierzchołek może być zajęty przez co najwyżej jeden token. Wyróżniamy dwa kolory tokenów, biały i czarny, każdy gracz może przemieszczać tylko własne tokeny. Gracze wykonują ruchy naprzemiennie. Ruch polega na wyborze dowolnego tokena własnego koloru i przesunięciu go na dowolnego niezajętego przez inny token sąsiada, zgodnie z kierunkiem skierowanej krawędzi. Gracz, który nie może wykonać ruchu przegrywa. W pracy dowodzimy, że powyższa gra należy do problemów PSPACE-zupełnych już w przypadku acyklicznych grafów planarnych.

Autorzy

• prof. dr hab. inż. Dariusz Dereniowski link otwiera się w nowej karcie