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.
Authors
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.1016/j.jcta.2010.03.011
- Category
- Publikacja w czasopiśmie
- Type
- artykuł w czasopiśmie wyróżnionym w JCR
- Language
- angielski
- Publication year
- 2011
Source: MOSTWiedzy.pl - publication "The complexity of node blocking for dags" link open in new tab
