The capture time of the hypercube (Q1953506): Difference between revisions
From MaRDI portal
Set profile property. |
Changed an Item |
||
Property / arXiv ID | |||
Property / arXiv ID: 1308.3354 / rank | |||
Normal rank |
Revision as of 00:06, 19 April 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