Wyszukiwarka
Abstrakt
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.
Cytowania
-
0
CrossRef
-
0
Web of Science
-
1
Scopus
Cytuj jako
Pełna treść
pobierz publikację
pobrano 10 razy
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.jcta.2010.03.011
- Licencja
- Copyright (2010 Elsevier Inc)
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
JOURNAL OF COMBINATORIAL THEORY SERIES A
nr 118,
strony 248 - 256,
ISSN: 0097-3165 - Język:
- angielski
- Rok wydania:
- 2011
- Opis bibliograficzny:
- 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:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.jcta.2010.03.011
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 57 razy