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.
Authors
- prof. dr hab. inż. Dariusz Dereniowski link open in new tab ,
- Danny Dyer,
- Ryan M. Tifenbach,
- Boting Yang
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.1016/j.tcs.2015.03.022
- Category
- Publikacja w czasopiśmie
- Type
- artykuł w czasopiśmie wyróżnionym w JCR
- Language
- angielski
- Publication year
- 2015
Source: MOSTWiedzy.pl - publication "The complexity of zero-visibility cops and robber" link open in new tab
