کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
433786 689628 2016 29 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Complexity and monotonicity results for domination games
ترجمه فارسی عنوان
نتایج پیچیدگی و تک رنگی برای بازی های سلطه
کلمات کلیدی
گراف بازی جستجو، پلیس و بازی های دزدی، بازی های سلطه جستجو پیچیدگی پارامتریک، یکنواختی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

In this paper we study Domination Games, a class of games introduced by Fomin, Kratsch, and Müller in [8]. Domination games are a variant of the well-known graph searching games (also called cops and robber games), where a number of cops tries to capture a robber hiding on the vertices of a graph. Variants of these games are often used to provide a game-theoretic characterization of important graph parameters such as pathwidth, treewidth, and hypertreewidth.We are primarily interested in questions concerning the complexity and monotonicity of these games. We show that dominating games are computationally much harder than standard cops and robber games and establish strong non-monotonicity results for various notions of monotonicity that arise naturally in the context of domination games. Answering a question of [8], we show that there are graphs where the shortest winning strategy for a minimal number of cops must necessarily be of exponential length.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 628, 16 May 2016, Pages 1–29
نویسندگان
, ,