Search
Results
-
A Tight Lower Bound for Semi-Synchronous Collaborative Grid Exploration
(2018)Leibniz International Proceedings in Informatics (LIPIcs) ~ 32nd International Symposium on Distributed Computing (DISC 2018)Recently, there has been a growing interest in grid exploration by agents with limited capabilities. We show that the grid cannot be explored by three semi-synchronous finite automata, answering an open question by Emek et al. [TCS'15] in the negative. In the setting we consider, time is divided into discrete steps, where in each step, an adversarially selected subset of the agents executes one look-compute-move cycle. The agents operate ...Conference Paper -
A Tight Lower Bound for the Capture Time of the Cops and Robbers Game
(2017)Leibniz International Proceedings in Informatics (LIPIcs) ~ 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)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 ...Conference Paper