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