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?
- 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