O(Diamater) is the time complexity for any node to receive a message from any other node. If there is such an algorithm that every node flooding a message consisting of some information about the neighbors and itself, would it be possible to learn all the graph topology in O(Diameter)?

What content should you message to others (or forward other messages), so that all the nodes will be able to learn the graph topology by O(Diameter)?

  • $\begingroup$ I can't parse your question. I don't understand what the "If..." part is saying. Also, I'm not sure what you mean by "by O(Diameter)". Are you talking about number of messages sent? Latency? Do you require all messages be constant-length? If we send a long message, is the time required to do that proportional to the length of the message, or is it considered constant time? I suggest you articulate the model of computation carefully in your question as it is likely to affect the answer. $\endgroup$ – D.W. Jul 3 '18 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.