Searching with mobile agents in networks with liars
We present deterministic algorithms to search for an item s contained in a node of a network, without prior knowledge of its exact location. Each node of the network has a database that will answer queries of the form "how do I get to s?" by responding with the first edge on a shortest path to the node containing s. It may happen that some nodes, called liars, give bad advice. If the number of liars k is bounded, we show different strategies to find the item depending on the topology of the network. In particular we consider the complete graph, ring, torus, hypercube and bounded degree trees.
|Journal||Discrete Applied Mathematics|
Hanusse, N. (Nicolas), Kranakis, E, & Krizanc, D. (Danny). (2004). Searching with mobile agents in networks with liars. In Discrete Applied Mathematics (Vol. 137, pp. 69–85). doi:10.1016/S0166-218X(03)00189-6