Geodesic
The capture time of the hypercube
Anthony Bonato ; Przemysław Gordinowicz ; Bill Kinnersley ; Paweł Prałat1
1Department of Mathematics Ryerson University
The electronic journal of combinatorics, Tome 20 (2013) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/2921
Classification : 05C57, 05C65, 91A24, 05C80
Mots-clés : cops and robbers, capture time, hypercube, coupon-collector problem

Anthony Bonato    ; Przemysław Gordinowicz    ; Bill Kinnersley    ; Paweł Prałat  1

1 Department of Mathematics Ryerson University 
@article{10_37236_2921,
     author = {Anthony Bonato and Przemys{\l}aw Gordinowicz and Bill Kinnersley and Pawe{\l} Pra{\l}at},
     title = {The capture time of the hypercube},
     journal = {The electronic journal of combinatorics},
     year = {2013},
     volume = {20},
     number = {2},
     doi = {10.37236/2921},
     zbl = {1266.05096},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/2921/}
}
TY  - JOUR
AU  - Anthony Bonato
AU  - Przemysław Gordinowicz
AU  - Bill Kinnersley
AU  - Paweł Prałat
TI  - The capture time of the hypercube
JO  - The electronic journal of combinatorics
PY  - 2013
VL  - 20
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/2921/
DO  - 10.37236/2921
ID  - 10_37236_2921
ER  - 
%0 Journal Article
%A Anthony Bonato
%A Przemysław Gordinowicz
%A Bill Kinnersley
%A Paweł Prałat
%T The capture time of the hypercube
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/2921/
%R 10.37236/2921
%F 10_37236_2921
Anthony Bonato; Przemysław Gordinowicz; Bill Kinnersley; Paweł Prałat. The capture time of the hypercube. The electronic journal of combinatorics, Tome 20 (2013) no. 2. doi: 10.37236/2921

Cité par Sources :