The optimal capture time of the one-cop-moves game

摘要

In this paper we consider the optimal capture time of the one-cop-moves game. Given a graph with a set of cops and a single robber located on vertices, in each round of the game, the robber moves from her location to an adjacent vertex and then one of the cops moves from his location to an adjacent vertex. We want to find a strategy for cops that minimizes the time taken by the cops to capture the robber. In particular, we explore algorithms regarding this game on trees involving two cops and a single robber. We present four algorithms that compute optimal-search, monotonic-search, greedy-search and balanced-search strategies, respectively, for different variants of the game depending on robber's visibility. We show performance ratios when some of them are considered as approximation algorithms for finding the optimal capture time. (C) 2015 Elsevier B.V. All rights reserved.