How to Hunt an Invisible Rabbit on a Graph

How to Hunt an Invisible Rabbit on a Graph
复制标题

如何在图表上寻找隐形兔子

DOI：
10.1016/j.ejc.2015.08.002
复制
发表时间：
2015
期刊：
ArXiv
影响因子：
--
通讯作者：
Michal Pilipczuk
Michal Pilipczuk
中科院分区：
--
文献类型：
--
作者：
T. V. Abramovskaya;F. Fomin;P. Golovach;Michal Pilipczuk

文献摘要

被引文献

相似文献

摘要 我们在图上研究了猎人与兔子游戏，其中一组猎人试图抓住一只看不见的兔子，这只兔子在每一轮都被迫沿着图的边缘滑动。我们证明了在 (n× m) 网格上获胜所需的最小猎人数量是⌊ min {n, m} 2⌋+ 1。我们还表明，在 n 顶点树上这个数字的极值在 Ω (log n/log log n) 和 O (log n) 之间。
Abstract We investigate Hunters & Rabbit game on graphs, where a set of hunters tries to catch an invisible rabbit that is forced to slide along an edge of a graph at every round. We show that the minimum number of hunters required to win on an (n× m)-grid is⌊ min {n, m} 2⌋+ 1. We also show that the extremal value of this number on n-vertex trees is between Ω (log n/log log n) and O (log n).