The complexity of zero-visibility cops and robber - Publikacja - MOST Wiedzy

Wyszukiwarka

The complexity of zero-visibility cops and robber

Abstrakt

We consider the zero-visibility cops & robber game restricted to trees. We produce a characterisation of trees of copnumber k and We consider the computational complexity of the zero-visibility Cops and Robber game. We present a heavily modified version of an already-existing algorithm that computes the zero-visibility copnumber of a tree in linear time and we show that the corresponding decision problem is NP-complete on a nontrivial class of graphs.

Cytowania

  • 8

    CrossRef

  • 5

    Web of Science

  • 8

    Scopus

Pełna treść

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

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:
THEORETICAL COMPUTER SCIENCE nr 607, strony 135 - 148,
ISSN: 0304-3975
Język:
angielski
Rok wydania:
2015
Opis bibliograficzny:
Dereniowski D., Dyer D., Tifenbach R., Yang B.: The complexity of zero-visibility cops and robber// THEORETICAL COMPUTER SCIENCE. -Vol. 607, nr. part 2 (2015), s.135-148
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.tcs.2015.03.022
Weryfikacja:
Politechnika Gdańska

wyświetlono 27 razy

Publikacje, które mogą cię zainteresować

Meta Tagi