Cop and Robber Game and Hyperbolicity

Wednesday, April 30, 2014 - 9:00am - 9:50am
Keller 3-180
Victor Chepoi (Aix-Marseille Université)
In the talk, after an introduction of the cop and robber game and Gromov hyperbolicity, we will outline the proof that all cop-win graphs G in the game in which the robber and the cop move at different speeds s and s' with s'for any r>0, this establishes a new --game-theoretical-- characterization of Gromov hyperbolicity. Using these results, we describe a simple constant-factor approximation of hyperbolicity of a graph on n vertices running in O(n^2log n) time. Joint work with J. Chalopin, P. Papasoglu, and T. Pecatte.
MSC Code: