The capture time of the hypercube (Q1953506): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 16:29, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The capture time of the hypercube |
scientific article |
Statements
The capture time of the hypercube (English)
0 references
7 June 2013
0 references
Summary: 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.
0 references
cops and robbers
0 references
capture time
0 references
hypercube
0 references
coupon-collector problem
0 references