Cops and Robbers from a distance

作     者：Bonato, Anthony Chiniforooshan, Ehsan Pralat, Pawel 

作者机构：Ryerson Univ Dept Math Toronto ON Canada Univ Western Ontario Dept Comp Sci London ON Canada W Virginia Univ Dept Math Morgantown WV 26506 USA 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2010年第411卷第43期

页      面：3834-3844页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NSERC MITACS 

主　　题：Graphs Cop number Polynomial time algorithm Strong product NP-hard Random graph 

摘      要：Cops and Robbers is a pursuit and evasion game played on graphs that has received much attention. We consider an extension of Cops and Robbers, distance k Cops and Robbers, where the cops win if at least one of them is of distance at most k from the robber in G. The cop number of a graph G is the minimum number of cops needed to capture the robber in G. The distance k analogue of the cop number, written c(k)(G), equals the minimum number of cops needed to win at a given distance k. We study the parameter c(k) from algorithmic, structural, and probabilistic perspectives. We supply a classification result for graphs with bounded c(k)(G) values and develop an O(n(2s+3)) algorithm for determining if ck(G) = 0, it is shown that c(k)(G) as a function of the average degree d(n) = pn forms an intriguing zigzag shape. (C) 2010 Elsevier B.V. All rights reserved.