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 n...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2004-02, Vol.137 (1), p.69-85
Main Authors: Hanusse, Nicolas, Kranakis, Evangelos, Krizanc, Danny
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Combinatorics
Combinatorics. Ordered structures
Computer Science
Computer science
control theory
systems
Data processing. List processing. Character string processing
Exact sciences and technology
Mathematics
Memory organisation. Data processing
Other
Sciences and techniques of general use
Software
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0166-218X
1872-6771
DOI:10.1016/S0166-218X(03)00189-6