کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
437773 690184 2015 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 588, 11 July 2015, Pages 96–113
نویسندگان
, ,