ILCINKAS , 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...

We study the problem of finding a destination node $t$ by a mobile agent in an unreliable network having the structure of an unweighted graph, in a model first proposed by Hanusse {\it et al.}~\cite{HKK00,HKKK08}. Each node of the network is able to give advice concerning the next node to visit so as to go closer to the target $t$....

Nous étudions le problème consistant à trouver une destination t dans un réseau, non fiable, grâce à un agent mobile. Chaque noeud du réseau peut donner un conseil quant au prochain sommet à visiter pour se rapprocher de t. Malheureusement, k noeuds, appelés menteurs, donnent de mauvais conseils. Il est connu que pour un graphe G de n sommets...

We study the problem of finding a destination node t by a mobile agent in an unreliable network having the structure of an unweighted graph, in a model first proposed by Hanusse et al [20, 21]. Each node of the network is able to give advice concerning the next node to visit so as to go closer to the target t. Unfortunately, exactly k of the...