Gallager Humblet Spira Algorithm Assignment Help

Gallager Humblet Spira Algorithm

  • much more complicated however much like Kruskal’s
  • no root provided, edge weights thought to become distinct
  • MST built up in fragments
  • Initially every node within its own fragment
  • fragments merge, lastly only one fragment
  • outgoing edge – edge which will go in between two fragments
  • known outcome – min. wt. outgoing edge of a fragment usually within MST

Gallager Humblet Spira Algorithm Issues

  • how exactly does the node find its min. wt. outgoing edge?
  • how exactly does the fragment finds its min. wt. outgoing edge?
  • Whenever will two fragments merge?
  • how exactly does the two fragments merge?

Some definitions

  • Each node has three stateside
    • Sleeping – initial state
    • Find – currently finding the fragment’s min. wt. outgoing edge
    • Found – found the min. wt. outgoing edge
  • Each fragment has a level
    • Initially, each node is in a fragment of level 0