Search
Abstract
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.
Citations
-
0
CrossRef
-
0
Web of Science
-
1
Scopus
Cite as
Full text
download paper
downloaded 10 times
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.jcta.2010.03.011
- License
- Copyright (2010 Elsevier Inc)
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
JOURNAL OF COMBINATORIAL THEORY SERIES A
no. 118,
pages 248 - 256,
ISSN: 0097-3165 - Language:
- English
- Publication year:
- 2011
- Bibliographic description:
- Dereniowski D.: The complexity of node blocking for dags// JOURNAL OF COMBINATORIAL THEORY SERIES A. -Vol. 118, nr. Iss. 1 (2011), s.248-256
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.jcta.2010.03.011
- Verified by:
- Gdańsk University of Technology
seen 58 times