论文标题
警察和永恒强盗的游戏
The Game of Cops and Eternal Robbers
论文作者
论文摘要
我们介绍了警察和永恒的强盗游戏在图形上玩的游戏，那里有许多强盗在游戏的独特戏剧中依次出现。正面整数$ t $是固定的，并且警察必须在每场比赛中最多捕获强盗。 The associated optimization parameter is the eternal cop number, denoted by $c_t^{\infty},$ which equals the eternal domination number in the case $t=1,$ and the cop number for sufficiently large $t.$ We study the complexity of Cops and Eternal Robbers, and show that game is NP-hard when $t$ is a fixed constant and EXPTIME-complete for large values of $t$.我们确定路径和周期的$ C_T^{\ infty} $的精确值。研究了永恒的COP编号以进行缩回，并采用这种方法来给出树木的边界，以及强大的和笛卡尔的网格。
We introduce the game of Cops and Eternal Robbers played on graphs, where there are infinitely many robbers that appear sequentially over distinct plays of the game. A positive integer $t$ is fixed, and the cops are required to capture the robber in at most $t$ time-steps in each play. The associated optimization parameter is the eternal cop number, denoted by $c_t^{\infty},$ which equals the eternal domination number in the case $t=1,$ and the cop number for sufficiently large $t.$ We study the complexity of Cops and Eternal Robbers, and show that game is NP-hard when $t$ is a fixed constant and EXPTIME-complete for large values of $t$. We determine precise values of $c_t^{\infty}$ for paths and cycles. The eternal cop number is studied for retracts, and this approach is applied to give bounds for trees, as well as for strong and Cartesian grids.
