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.

Discrete Applied Mathematics
School of Computer Science

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