کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437773 | 690184 | 2015 | 18 صفحه PDF | دانلود رایگان |
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.
Journal: Theoretical Computer Science - Volume 588, 11 July 2015, Pages 96–113