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.
Autorzy
- prof. dr hab. inż. Dariusz Dereniowski link otwiera się w nowej karcie ,
- Danny Dyer,
- Ryan M. Tifenbach,
- Boting Yang
Informacje dodatkowe
- DOI
- Cyfrowy identyfikator dokumentu elektronicznego link otwiera się w nowej karcie 10.1007/978-3-319-08016-1_6
- Kategoria
- Aktywność konferencyjna
- Typ
- materiały konferencyjne indeksowane w Web of Science
- Język
- angielski
- Rok wydania
- 2014
Źródło danych: MOSTWiedzy.pl - publikacja "The Complexity of Zero-Visibility Cops and Robber" link otwiera się w nowej karcie
