Advertisement
Help Keep Boards Alive. Support us by going ad free today. See here: https://subscriptions.boards.ie/.
If we do not hit our goal we will be forced to close the site.

Current status: https://keepboardsalive.com/

Annual subs are best for most impact. If you are still undecided on going Ad Free - you can also donate using the Paypal Donate option. All contribution helps. Thank you.
https://www.boards.ie/group/1878-subscribers-forum

Private Group for paid up members of Boards.ie. Join the club.
Hi all, please see this major site announcement: https://www.boards.ie/discussion/2058427594/boards-ie-2026

Asynchronous Message Passing, BFS Algorithm

  • 03-05-2015 07:36PM
    #1
    humham0517
    Registered Users, Registered Users 2 Posts: 3 ✭


    distributed Bellman-Ford Algorithm for constructing a BFS tree in
    an asynchronous message passing system. The time complexity of the algorithm is O(D) and the message complexity is O(mn), where D is the diameter of the graph, n the number of nodes and m the number of edges. The number of edges in any graph is in O(n2), which implies an upper bound of O(n3) on the number of messages. Find a graph and an execution of the algorithm in which (n3) messages are sent and explain your solution


Advertisement