[0007gaurav]

Hi Everybody!!

I am having a tough time while understanding this paper. The point is that I didn't understood about how they carrying out there process..

H. N. Gabow, Z. Galil, T. Spencer, and R. E. Tarjan. 1986. Efficient algorithms for finding
minimum spanning trees in undirected and directed graphs. Combinatorica 6:109{122.

Does anybody have some animation or ppt through which this process can be explained??
I'll be really really thankful to you.

[macosxnerd101]

I've got tutorials on Kruskal's MST Algorithm and Dijkstra's Algorithm. Prim's MST Algorithm is basically the same as Dijkstra's with a couple minor tweaks. It's still a greedy breadth-first traversal, but with the constraint of having to cover all the vertices and not allowing for any circuits.

Hope this helps some.

[0007gaurav]

macosxnerd101, on 10 September 2011 - 11:06 AM, said:

I've got tutorials on Kruskal's MST Algorithm and Dijkstra's Algorithm. Prim's MST Algorithm is basically the same as Dijkstra's with a couple minor tweaks. It's still a greedy breadth-first traversal, but with the constraint of having to cover all the vertices and not allowing for any circuits.

Hope this helps some.

Thanks a lot for your reply. The problem is not with prims and kruskal, but it is with advance algorithm given by gabow & tarzan.. The above post doesn't give answer to my problem..

[macosxnerd101]

Is the paper free? Link me to it so I can take a look.

[0007gaurav]

macosxnerd101, on 10 September 2011 - 11:17 AM, said:

Is the paper free? Link me to it so I can take a look.

Yes.. here is the link

http://www.springerl...38n1xl59371v7j/

direct link:
http://www.springerl...7j/fulltext.pdf

I have problem with what is beta function here and how exactly is expansion of tree taking place..

[macosxnerd101]

Just read over section two- very interesting read, btw! It looks like a very Kruskal implementation. Essentially, you have a forest of unconnected vertices. Pick one. Next create a Heap, which will store Trees as you add them. Next you have a Set of Packets. Each Packet contains the Edges for a given vertex in the Tree.

Now, while the Set has Packets, get a Packet. Discard the Packet if it is empty. Now, find the Tree with the Vertex at the other end of the Edge (the one that is not in the original Tree). If the other vertex is not in the Heap, add it. If the edge comes to a lower cost than the one in the Tree, replace the entry with the lower-cost one. Then push that old entry back into its packet, and that packet back onto the Set.

Once you finish, just connect the original Tree to the minimum Tree in the heap. This assumes that the heap has k elements.

Adding the beta function just determines packet size. The packets for each vertex are of size p, save for up to one packet per vertex.

Does this help some?