SOGUET , David

Blin et al. (TCS 2008) proposed a distributed protocol enabling the smallest possible number of searchers to clear any unknown graph in a decentralized manner. However, the strategy that is actually performed lacks of an important property, namely the monotonicity. This paper deals with the smallest number of searchers that are necessary and...

Fraigniaud et al. [L. Blin, P. Fraigniaud, N. Nisse, S. Vial, Distributing chasing of network intruders, in: 13th Colloquium on Structural Information and Communication Complexity, SIROCCO, in: LNCS, vol. 4056, Springer-Verlag, 2006, pp. 70--84] introduced a new measure of difficulty for a distributed task in a network. The smallest number of...

Fraigniaud {\it et al.} (2006) introduced a new measure of difficulty for a distributed task in a network. The smallest {\it number of bits of advice} of a distributed problem is the smallest number of bits of information that has to be available to nodes in order to accomplish the task efficiently. Our paper deals with the number of bits of...