Wyszukiwarka
Abstrakt
The game of Cops and ∞-fast Robber is played by two players, one controlling c cops, the other one robber. The players alternate in turns: all the cops move at once to distance at most one each, the robber moves along any cop-free path. Cops win by sharing a vertex with the robber, the robber by avoiding capture indefinitely. The game was proposed with bounded robber speed by Fomin et al. in “Pursuing a fast robber on a graph”, generalizing a well-known game of Cops and Robber which has robber speed 1. We answer their open question about the computational complexity of the game on interval graphs with ∞-fast robber, showing it to be polynomially decidable. We also generalize the concept of k-defensive domination introduced by Farley and Proskurowski in “Defensive Domination” to A--defensive domination and use it as a main tool in our proof. The generalization allows specifying arbitrary attacks and limiting the number of defenders of each vertex. While this problem is NP-complete even for split graphs, we show that A-defensive domination is decidable in polynomial time on interval graphs.
Cytowania
-
5
CrossRef
-
0
Web of Science
-
5
Scopus
Autorzy (3)
-
Tomáš Gavenčiak
- Charles University Department of Applied Mathematics
-
Jan Kratochvíl
- Charles University Department of Applied Mathematics
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.tcs.2018.09.031
- Licencja
- Copyright (2018 Elsevier B.V.)
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach
- Opublikowano w:
-
THEORETICAL COMPUTER SCIENCE
nr 794,
strony 47 - 58,
ISSN: 0304-3975 - Język:
- angielski
- Rok wydania:
- 2019
- Opis bibliograficzny:
- Dereniowski D., Gavenčiak T., Kratochvíl J.: Cops, a fast robber and defensive domination on interval graphs// THEORETICAL COMPUTER SCIENCE -Vol. 794, (2019), s.47-58
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.tcs.2018.09.031
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 140 razy
Publikacje, które mogą cię zainteresować
The complexity of zero-visibility cops and robber
- D. Dereniowski,
- D. Dyer,
- R. M. Tifenbach
- + 1 autorów
The Complexity of Zero-Visibility Cops and Robber
- D. Dereniowski,
- D. Dyer,
- R. M. Tifenbach
- + 1 autorów
Zero-Visibility Cops and Robber Game on a Graph
- D. Dereniowski,
- D. Dyer,
- R. M. Tifenbach
- + 1 autorów
Zero-visibility cops and robber and the pathwidth of a graph
- D. Dereniowski,
- D. Dyer,
- R. M. Tifenbach
- + 1 autorów