Name
Abstract | ||
|---|---|---|
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^2^s^+^3) algorithm for determining if c"k(G)@?s for s fixed. We prove that if s is not fixed, then computing c"k(G) is NP-hard. Upper and lower bounds are found for c"k(G) in terms of the order of G. We prove that (nk)^1^/^2^+^o^(^1^)@?c"k(n)=O(nlog(2nk+1)log(k+2)k+1), where c"k(n) is the maximum of c"k(G) over all n-vertex connected graphs. The parameter c"k(G) is investigated asymptotically in random graphs G(n,p) for a wide range of p=p(n). For each k=0, it is shown that c"k(G) as a function of the average degree d(n)=pn forms an intriguing zigzag shape. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.tcs.2010.07.003 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
evasion game,random graph.,np-hard,. graphs,Polynomial time algorithm,minimum number,distance k,Cop number,NP-hard,cop number,distance k Cops,Strong product,average degree,strong product,graph G,bounded c,polynomial time algorithm,classification result,Graphs,Random graph,distance k analogue | Journal | 411 |
Issue | ISSN | Citations |
43 | Theoretical Computer Science | 16 |
PageRank | References | Authors |
1.32 | 13 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anthony Bonato | 1 | 156 | 18.57 |
| Ehsan Chiniforooshan | 2 | 118 | 16.38 |
| Pawe Praat | 3 | 27 | 2.84 |