Gromov hyperbolicity and cop and robber game
Închide
Articolul precedent
Articolul urmator
528 1
Ultima descărcare din IBN:
2023-06-14 21:17
SM ISO690:2012
CHALOPIN, J., CEPOI, Vasile, PAPASOGLU, P., PECATTE, T.. Gromov hyperbolicity and cop and robber game. In: Conference of Mathematical Society of the Republic of Moldova, 19-23 august 2014, Chișinău. Chișinău: "VALINEX" SRL, 2014, 3, pp. 334-339. ISBN 978-9975-68-244-2.
EXPORT metadate:
Google Scholar
Crossref
CERIF

DataCite
Dublin Core
Conference of Mathematical Society of the Republic of Moldova
3, 2014
Conferința "Conference of Mathematical Society of the Republic of Moldova"
Chișinău, Moldova, 19-23 august 2014

Gromov hyperbolicity and cop and robber game

Pag. 334-339

Chalopin J., Cepoi Vasile, Papasoglu P., Pecatte T.
 
University de la Mediterranee
 
 
Disponibil în IBN: 10 octombrie 2017


Rezumat

In these notes, I will briefly describe the results which I will present in the talk entitled Cop and robber game and hyperbolicity, which are based on paper [3]. Generally speaking, our main result is that Gromov hyperbolicity can be characterized by the cop and robber game with speeds: in a ±-hyperbolic graph a slower cop can always catch a faster robber and, conversely, if in a graph G a slower cop can always catch a faster robber, then the hyperbolicity of G is quadratic in the speed of the cop. As a byproduct of our results, we obtain a constant factor approximation of hyperbolicity of an n-vertex graph in O(n2) time.

Cuvinte-cheie
geometry, computer science,

Gromov hyperbolicity, linear isoperimetric inequality, cop and robber game