The BFS algorithm given in Section 17.4.1 terminates explicitly. Consider the al
ID: 3691179 • Letter: T
Question
The BFS algorithm given in Section 17.4.1 terminates explicitly. Consider the algo- rithm that terminates implicitly and operates as follows.
There are only two kinds of messages. One says “I am at level l,” for some number l. The other says “I am your child.” Initially, all the nodes, except for the leader who initiates computation, consider themselves as being at an infinitely large level. The initiator sends a message notifying its neighbors about its zero level. Upon receiving a message with a notification of being at some level i, the node checks if this is a new minimum level among the neighbors. If this is the case, then the node replies with a message notifying of becoming a child, and sends messages to the remaining neighbors notifying about being at level i + 1. Otherwise the node ignores the message about its neighbor being at level i. Time is counted until the last message is sent.
What are the communication and time complexities of this algorithm?
Explanation / Answer
DFS(v)
i i + 1
pre(v) i
active(v) 1
for all w adj(v) do
if pre(w) = 0 then DFS(w)
else if pre(w) > pre(v) then
else if active(w) = 0 then
else
active(v) 0
i i + 1
post(v) i
end DFS
running time will be O(m+n).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.