The Capture Time of the Hypercube
Copyright policy )The Capture Time of the Hypercube
In the game of Cops and Robbers, the capture time of a graph is the minimum number of moves needed by the cops to capture the robber, assuming optimal play. We prove that the capture time of the $n$-dimensional hypercube is $\Theta (n\ln n)$. Our methods include a novel randomized strategy for the players, which involves the analysis of the coupon-collector problem.
- Lodz University of Technology Poland
- Toronto Metropolitan University Canada
- University of Toronto Canada
FOS: Computer and information sciences, capture time, Discrete Mathematics (cs.DM), Games on graphs (graph-theoretic aspects), coupon-collector problem, Random graphs (graph-theoretic aspects), Hypergraphs, cops and robbers, hypercube, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Positional games (pursuit and evasion, etc.), Computer Science - Discrete Mathematics
FOS: Computer and information sciences, capture time, Discrete Mathematics (cs.DM), Games on graphs (graph-theoretic aspects), coupon-collector problem, Random graphs (graph-theoretic aspects), Hypergraphs, cops and robbers, hypercube, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Positional games (pursuit and evasion, etc.), Computer Science - Discrete Mathematics
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).7 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!