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.

Additional Metadata
Persistent URL dx.doi.org/10.1016/S0166-218X(03)00189-6
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