Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, July 06, 2017, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Jara Uitto
For the game of cops and robbers, it is known that in 1-cop-win graphs, the cop can capture the robber in O(n) time and that there exist graphs in which this capture time is tight. When k ≥ 2, a simple counting argument shows that in k-cop-win graphs, the capture time is at most O( n^(k+1) ), however, no non-trivial lower bounds were previously known; indeed, in their 2011 book, Bonato and Nowakowski ask whether this upper bound can be improved. We answer the question of Bonato and Nowakowski on the negative, proving that the O(n^(k+1) ) bound is asymptotically tight for any constant k ≥ 2. This yields a surprising gap in the capture time complexities between the 1-cop and the 2-cop cases.
Automatic MiSe System Software Version 1.4803M | admin login