http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
Two remarks on the game of Cops and Robbers
Yaroslav Shitov 대한수학회 2020 대한수학회보 Vol.57 No.1
We discuss two unrelated topics regarding \textit{Cops and Robbers}, a well-known pursuit-evasion game played on a simple graph. First, we address a recent question of Breen et al.~and prove the PSPACE-completeness of the \textit{cop throttling number}, that is, the minimal possible sum of the number $k$ of cops and the number $\operatorname{capt}(k)$ of moves that the robber can survive against $k$ cops under the optimal play of both sides. Secondly, we revisit a \textit{teleporting} version of the game due to Wagner; we disprove one of his conjectures and suggest a new related research problem.
TWO REMARKS ON THE GAME OF COPS AND ROBBERS
Shitov, Yaroslav Korean Mathematical Society 2020 대한수학회보 Vol.57 No.1
We discuss two unrelated topics regarding Cops and Robbers, a well-known pursuit-evasion game played on a simple graph. First, we address a recent question of Breen et al. and prove the PSPACE-completeness of the cop throttling number, that is, the minimal possible sum of the number k of cops and the number capt(k) of moves that the robber can survive against k cops under the optimal play of both sides. Secondly, we revisit a teleporting version of the game due to Wagner; we disprove one of his conjectures and suggest a new related research problem.