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

Abstract

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.

Citations

1

CrossRef
0

Web of Science
0

Scopus

Authors (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

Cite as

Full text

full text is not available in portal

full content of the article see on external site open in new tab

Keywords

Details

Category:: Conference activity
Type:: materiały konferencyjne indeksowane w Web of Science
Title of issue:: Frontiers in Algorithmics, FAW 2014 strony 60 - 70
Language:: English
Publication year:: 2014
Bibliographic description:: 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:: Digital Object Identifier (open in new tab) 10.1007/978-3-319-08016-1_6
Verified by:: Gdańsk University of Technology