The capture time of a graph
The capture time of a graph
复制标题
图表的捕获时间
DOI：
10.1016/j.disc.2008.04.004
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Jan Kratochvíl
中科院分区：
文献类型：
--
作者：
A. Bonato;P. Golovach;G. Hahn;Jan Kratochvíl
我们考虑在有限和可数无限连通图上进行的警察和强盗的博弈。在COP-WIN图上考虑了博弈的长度，得到了一个新的参数--图的捕获时间。当n个顶点的COP-WIN图的捕获时间在n−3以上时，对于包括弦图在内的一大类图来说，一半的顶点数是足够的。给出了COP-WIN图的例子，这些图有唯一的角且捕获时间在顶点数的一个小的可加常数内。我们考虑捕获时间与顶点数之比，并将捕获时间密度的概念推广到无限图。对于无限随机图，捕获时间密度可以是[0，1]中的任意实数。我们还考虑了当需要多个警察才能获胜时的抓捕时间。当警察数目k固定时，捕获时间可以用多项式算法计算，但对于每固定t次，k个警察是否能在不超过t步的情况下捕获强盗是NP-完全问题。
We consider the game of Cops and Robbers played on finite and countably infinite connected graphs. The length of games is considered on cop-win graphs, leading to a new parameter, the capture time of a graph. While the capture time of a cop-win graph on n vertices is bounded above by n−3, half the number of vertices is sufficient for a large class of graphs including chordal graphs. Examples are given of cop-win graphs which have unique corners and have capture time within a small additive constant of the number of vertices. We consider the ratio of the capture time to the number of vertices, and extend this notion of capture time density to infinite graphs. For the infinite random graph, the capture time density can be any real number in [0,1]. We also consider the capture time when more than one cop is required to win. While the capture time can be calculated by a polynomial algorithm if the number k of cops is fixed, it is NP-complete to decide whether k cops can capture the robber in no more than t moves for every fixed t.