• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Graph-theoretic concepts in computer science >Distance d-Domination Games
【24h】

Distance d-Domination Games

机译：距离d统治游戏

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study graph searching games where a number of cops try to capture a robber that is hiding in a system of tunnels modelled as a graph. While the current position of the robber is unknown to the cops, each cop can see a certain radius d around his position. For the case d = 1 these games have been studied by Fomin, Kratsch and Mueller [7] under the name domination games. 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 graph searching games where the cops only see their own vertex and establish strong non-monotonicity results for various notions of monotonicity which arise naturally in the context of domination games. Answering a question of [7], we show that there exists graphs for which the shortest winning strategy for a minimal number of cops must necessarily be of exponential length. On the positive side, we establish tractability results for graph classes of bounded degree.
机译：我们研究图搜索游戏，其中许多警察试图捕获藏在以图为模型的隧道系统中的强盗。虽然警察不知道强盗的当前位置，但每个警察可以在其位置周围看到一定的半径d。对于d = 1的情况，这些游戏已经由Fomin，Kratsch和Mueller [7]以“统治游戏”的名称进行了研究。我们主要对有关这些游戏的复杂性和单调性的问题感兴趣。我们证明了控制游戏比标准图搜索游戏在计算上要困难得多，在标准图形搜索游戏中，警察只能看到自己的顶点并针对在控制游戏中自然产生的各种单调性概念建立强大的非单调性结果。回答问题[7]，我们表明存在图，对于图最小的警察来说，最短的获胜策略必须具有指数长度。在积极方面，我们为有界度的图类建立了易处理性结果。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号