Wyszukiwarka
Abstrakt
We examine the zero-visibility cops and robber graph searching model, which differs from the classical cops and robber game in one way: the robber is invisible. We show that this model is not monotonic. We show that the zero-visibility copnumber of a graph is bounded above by its pathwidth and cannot be bounded below by any nontrivial function of the pathwidth. As well, we define a monotonic version of this game and show that the monotonic zero-visibility copnumber can be bounded both above and below by positive multiples of the pathwidth.
Cytowania
-
1 6
CrossRef
-
0
Web of Science
-
1 5
Scopus
Autorzy (4)
-
Danny Dyer
- Memorial University of Newfoundland, St. John’s, NL, Canada Department of Mathematics and Statistics
-
Ryan M. Tifenbach
- Memorial University of Newfoundland, St. John’s, NL, Canada Department of Mathematics and Statistics
-
Boting Yang
- University of Regina, Regina, SK, Canada Department of Computer Science
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
JOURNAL OF COMBINATORIAL OPTIMIZATION
nr 29,
wydanie 3,
strony 541 - 564,
ISSN: 1382-6905 - Język:
- angielski
- Rok wydania:
- 2015
- Opis bibliograficzny:
- Dereniowski D., Dyer D., Tifenbach R., Yang B.: Zero-visibility cops and robber and the pathwidth of a graph // JOURNAL OF COMBINATORIAL OPTIMIZATION. -Vol. 29, iss. 3 (2015), s.541-564
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s10878-014-9712-6
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 119 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
The complexity of zero-visibility cops and robber
- 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