The complexity of node blocking for dags - Publikacja - MOST Wiedzy

Wyszukiwarka

The complexity of node blocking for dags

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ść

pełna treść publikacji nie jest dostępna w portalu

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 37 razy

Publikacje, które mogą cię zainteresować

Meta Tagi