Computer Science – Computational Complexity
Scientific paper
2010-09-22
Computer Science
Computational Complexity
Scientific paper
In this paper we ask which properties of a distributed network can be computed from a little amount of local information provided by its nodes. The distributed model we consider is a restriction of the classical CONGEST (distributed) model and it is close to the simultaneous messages (communication complexity) model defined by Babai, Kimmel and Lokam. More precisely, 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 square?", "does G contain a triangle?" or "Is the diameter of G at most 3? 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 of arbitrary graphs.
Becker Florent
Matamala Martin
Nisse Nicolas
Rapaport Iván
Suchan Karol
No associations
LandOfFree
Adding a referee to an interconnection network: What can(not) be computed in one round does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Adding a referee to an interconnection network: What can(not) be computed in one round, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adding a referee to an interconnection network: What can(not) be computed in one round will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-638499