文档介绍：Discrete Applied Mathematics 137 (2004) 69–85
Searching with mobile agents in networks with
liars
Nicolas Hanussea;1 , Evangelos Kranakisb;∗;2 , Danny Krizancc;3
aLaBRI-CNRS, Universite Bordeaux I, 33405 Talence, France
bSchool ofComputer Science, Carleton University, Ottawa, Ont., Canada KIS 5B6
cDepartment ofMathematics, Wesleyan University, Middletown, CT 06459, USA
Received 28 October 2000; received in revised form 8 June 2002; accepted 15 October 2002
Abstract
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 ÿrst 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 di<erent strategies to ÿnd the item depending on the
topology of the network. In particular we consider the complete graph, ring, torus, hypercube
and bounded degree trees.
? 2003 Elsevier . All rights reserved.
1. Introduction
The current information explosion on the Internet makes appealing the idea of having
a “personal explorer” chasing down information on the web. These personal explorers
can be thought of as mobile programs that traverse the network and have the ability to
focus their e<orts and perform certain predetermined tasks. They have already found
A preliminary version of this paper has appeared in [10].
∗ Corresponding author.
E-mail addresses: ******@- (N. Hanusse), ******@ (E. Kranakis),
******@ (D. Krizanc).
1 R