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 | ||||||
|
||||||
Pag. 334-339 | ||||||
|
||||||
Descarcă PDF | ||||||
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 |
||||||
|