The Complexity of Zero-Visibility Cops and Robber

Dariusz Dereniowski; Danny Dyer; Ryan M. Tifenbach; Boting Yang

doi:10.1007/978-3-319-08016-1_6

The Complexity of Zero-Visibility Cops and Robber

Abstrakt

In this work we deal with the computational complexity aspects of the zero-visibility Cops and Robber game. We provide an algorithm that computes the zero-visibility copnumber of a tree in linear time and show that the corresponding decision problem is NP-complete even for the class of starlike graphs.

Cytowania

1

CrossRef
0

Web of Science
0

Scopus

Autorzy (4)

Dariusz Dereniowski prof. dr hab. inż.
Danny Dyer
- Memorial University of Newfoundland, Canada Dept. of Mathematics and Statistics
Ryan M. Tifenbach
- Memorial University of Newfoundland, Canada Dept. of Mathematics and Statistics
Boting Yang
- University of Regina, Canada Dept. of Computer Science

Cytuj jako

Pełna treść

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

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

Słowa kluczowe

Informacje szczegółowe

Kategoria:: Aktywność konferencyjna
Typ:: materiały konferencyjne indeksowane w Web of Science
Tytuł wydania:: Frontiers in Algorithmics, FAW 2014 strony 60 - 70
Język:: angielski
Rok wydania:: 2014
Opis bibliograficzny:: Dereniowski D., Dyer D., Tifenbach R., Yang B..: The Complexity of Zero-Visibility Cops and Robber, W: Frontiers in Algorithmics, FAW 2014, 2014, Springer International Publishing,.
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/978-3-319-08016-1_6
Weryfikacja:: Politechnika Gdańska