Wyszukiwarka
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
-
1 6
CrossRef
-
0
Web of Science
-
1 7
Scopus
Autorzy (4)
-
Danny Dyer
- Memorial University of Newfoundland Department of Mathematics and Statistics
-
Ryan M. Tifenbach
- University of Regina Department of Mathematics and Statistics
-
Boting Yang
- University of Regina Department of Mathematics and Statistics
Cytuj jako
Pełna treść
pobierz publikację
pobrano 30 razy
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.tcs.2015.03.022
- Licencja
- Copyright (2015 Elsevier B.V.)
Słowa kluczowe
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 148 razy
Publikacje, które mogą cię zainteresować
Zero-Visibility Cops and Robber Game on a Graph
- D. Dereniowski,
- D. Dyer,
- R. M. Tifenbach
- + 1 autorów
2013
Zero-visibility cops and robber and the pathwidth of a graph
- D. Dereniowski,
- D. Dyer,
- R. M. Tifenbach
- + 1 autorów
2015
The Complexity of Zero-Visibility Cops and Robber
- D. Dereniowski,
- D. Dyer,
- R. M. Tifenbach
- + 1 autorów
2014
Cops, a fast robber and defensive domination on interval graphs
- D. Dereniowski,
- T. Gavenčiak,
- J. Kratochvíl
2019