The capture time of the hypercube (Q1953506): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Anthony Bonato / rank | |||
Property / author | |||
Property / author: Anthony Bonato / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1308.3354 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A game of cops and robbers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The capture time of a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3090934 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3224100 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Cop-win graphs with maximum capture-time / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Cops and invisible robbers: the cost of drunkenness / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some remarks on cops and drunk robbers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On a game of policemen and robber / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The capture time of grids / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A game of cops and robbers played on products of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Vertex-to-vertex pursuit in a graph / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 11:39, 6 July 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