Networks Cannot Compute Their Diameter in Sublinear Time

Silvio Frischknecht, Stephan Holzer and Roger Wattenhofer

Abstract:
We study the problem of computing the diameter of a network in a distributed way. The model of distributed computation we consider is: in each synchronous round, each node can transmit a different (but) short message to each of its neighbors. We provide an lower bound for the number of communication rounds needed, where n denotes the number of nodes in the network. This lower bound is valid even if the diameter of the network is a small constant. We also show that a -approximation of the diameter requires rounds. Furthermore we use our new technique to prove an lower bound on approximating the girth of a graph by a factor
.

Guest: Stephan Holzer
Host: Chen Avin

Leave a Reply

Your email address will not be published.

165,000 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>