Networks Cannot Compute Their Diameter in Sublinear Time
Silvio Frischknecht, Stephan Holzer, Roger P. Wattenhofer · 2012
We study the problem of computing the diameter of a network in a distributed way. In the model of distributed computation we consider is node can transmit a different (but short) message to each of its neighbors each synchronous round. We provide an ˜ Ω(n) 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 (3/2 − ε)approximation of the diameter requires ˜ Ω ( √ n + D) rounds. Furthermore we use our new technique to prove an ˜ Ω ( √ n + D) lower bound on approximating the girth of a graph by a factor 2 − ε. 1