MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTEAdding a referee to an interconnection network: what can(not) be computed in one round?
par Nicolas Nisse
| Date : | 02/11/10 | | Time : | 10h30 | | Location : | Lagrange Gris |
In this talk we will analyze which properties of a distributed network
can be computed from a few amount of local information provided by its
nodes. Each of these n nodes -which only knows its own ID and the IDs of
its neighbors- is allowed to send a message of O(log n) bits to some
central entity, called the referee. Is it possible for the referee to
decide some basic structural properties of the network topology G? We
show that simple questions like "does G contain a triangle (resp., a
square)?" cannot be solved in general. On the other hand, the referee
can decode the messages in order to have full knowledge of G when G
belongs to many graph classes such as planar graphs, bounded treewidth
graphs and, more generally, bounded degeneracy graphs. We leave open
questions related to the connectivity and the diameter (of arbitrary
graphs).<br /><br />This a joint work with Florent Becker (LIFO, Orléans), Martin Matamala (DIM, U. de Chile), Ivan
Rapaport (DIM, U. de Chile), Karol Suchan (U. Adolfo Ibanez, Chili) and
Ioan Todinca (LIFO, Orléans)
Page des séminaires
| 
