wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Minimum Spanning tree 
        
(Message started by: The_Hawk on Apr 2^nd, 2009, 9:39am)

Title: Minimum Spanning tree
Post by The_Hawk on Apr 2^nd, 2009, 9:39am

Consider a weighted graph G with n vertices and m edges, such that weight on each edge is an integer between 0 and n. How can we find a minimum spanning tree for G in O(n log*n) ?

Title: Re: Minimum Spanning tree
Post by Hippo on Apr 2^nd, 2009, 10:11am

You don't have time to read entire input.

Title: Re: Minimum Spanning tree
Post by nks on Apr 2^nd, 2009, 11:53pm

Do these alogs not work in O(n log*n) ?

* Reverse-Delete algorithm
* Dijkstra's algorithm
* Spanning tree protocol, used in switched networks
* Edmonds's algorithm
* Borůvka's algorithm
* Kruskal's algorithm
* Prim's algorithm
* Distributed minimum spanning tree

Title: Re: Minimum Spanning tree
Post by towr on Apr 3^rd, 2009, 12:07am

on 04/02/09 at 23:53:45, nks wrote:

Do these alogs not work in O(n log*n) ?

Not if you include reading the input, which is O(n²) in the number of vertices.

And it depends on the datastructure as well. e.g. Prim's algorithm (http://en.wikipedia.org/wiki/Prim%27s_algorithm) isn't O(n log n) if the graph is represented as a adjacency matrix or fibonacci heap + adjacency list.

Title: Re: Minimum Spanning tree
Post by Hippo on Apr 3^rd, 2009, 6:54am

I suppose he means O(m log* n) where log*n is the number of times 2^k must be applied to get above n. In that case Fredman-Tarjan algorithm fullfills the requirements.

(Fibonacci heaps restricted in size to bound guaranting whole phase working in O(m), used in seveal time restarted Dijkstra like algorithm, than removing edges inside trees and from duplicate edges among trees taking the minimal one. In next phase whole tree is represented by one vertex therefore the bound size for the heap increases exponentially. This is why log*n phases suffices.)

P.S.: Of course input must be given as a list of edges (with weights).

Title: Re: Minimum Spanning tree
Post by nakli on Jul 30^th, 2010, 12:00am

A paper here (http://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/efficient%20algorithm%20for%20funding.pdf') does it in O(n log n+m) for directed and even better for undirected.
It improves on the Fredman-Tarjan algorithm as mentioned by Hippo, which uses fibonacci heaps (http://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/fibonacci%20heaps.pdf) - a special data structure.

1. Can anyone explain the F-heap data structure in a simple manner, and perhaps
2. give a pseudo-code for the algorithm in the paper mentioned.
3. I am specially interested in directed graphs. Is it even better than Edmond's Algorithm (http://en.wikipedia.org/wiki/Edmonds%27s_algorithm) ?

Title: Re: Minimum Spanning tree
Post by Hippo on Aug 7^th, 2010, 4:31pm

I don't know what MST means in directed graphs.

To the Fibonacci heaps ... I don't expect I could briefly explain what did tarjan on the paper you pointed out.
... I usually describe Fibonacci heaps as the most lazy heaps ... avoid comparing keys whenever possible.
But I actually recomend "one tree" variant.

So what the FH did ... whenever you update FH (inserts /deletes/decrements), you don't mind finding new minimum. You just maintain set of candidates (in double linked lilst).

When you are finding a minimum, it's time for comparisions. But you don't compare the candidates arbitrary as you wanted to avoid wide "comparison result" trees. Each node has assigned rank (Initially 0).
You are trying to compare only nodes of the same rank. If you did it link the higher key to smaller key and increase rank of the resulting root.

You maintain invariant that size of the subtree under node of rank r is at least q^r (for a 1<q\le 2 ... actually the golden ratio, but to be proved later).
... this is maintained by this kind of linking.

The invariant guarantees the rank cannot exceed O(\log n).

But of course after you link candidates of the same rank ... a set of candidates of distinct ranks remains.
But as the ranks are distinct, the size of the set is O(log n). Now "one-tree" variant differs from the one presented by Tarjan. Tarjan let's you find minimum among this set with no influence to the structure.
I recommend to link bigger key to smaller one but not increasing the rank of the resulting root.

This is OK, but the analysis is a bit more complicated.
You must add the number of edges "nonincreasing rank" to the potential (together with the number of candidates).

You could made analysis such that amortised cost of FindMin, Insert, and Decrement are O(1) while the DeleteMin is O(log n).

This is because each link during FindMin is payed by decrement of candidate number. Complication is with paying the "rank nonincreasing edges". But they can be paid by previous DeleteMin (increasing it's cost by another O(log n) plus the number of candidates created by Inserts and Decrements since the last FindMin.

DeleteMin just deletes minimum and it's son's connects to the list of candidates. These sons are of two kinds ... either increasing rank, but there is at most O(log n) of them or nonincreasing rank, but in that case they are just moved from one potential to an other.

Findmin is actually more complicated ... it's a bit tricky to made it in a way total time is equal to the number of comparisons (let as an excercise).

Insert just creates new candidate of rank 0 so the last operation to be mentioned is Decrement.

... Only edge from the decremented node to it's "defender" becomes obsolete so remove the decremented node from the list of brothers and remove it as it's father's son :) and decrement it's fathers rank. It becames new candidate. ... Look's easy, it's structurally correct, but the invariant would not hold!

The trick to maintain the invariant (required for O(log n) delete) is to mark a node whose son was removed or (whose son decremented rank). Whenever you have to remove other son or decrement rank of other son, decrement rank of the node as well and unmark it.

When you compute the minimal tree size of the tree with the root of rank r, you got the name of the heaps (homework again).

But as you mark only one node and can paid the process by unmarking nodes to work with, Decrement takes O(1) amortised as well. (Don't forget to pay for created edges not increasing rank from it.)

----------------
So this was briefly, but I suppose to read the full version would be better :)
----------------
And for the MST algorithm ...
1) run "dijsktra" from a vertex untill the heap is large or it is connected to already done tree ... repeat while there are nonvisited vertices/components ... this reduces number of components.
2) sort edges by bucket sort to find loops and duplicates among components. Discard nonminimal edges.
Recompute the size treshold for the step 1) to finish in O(m) and repeat (until 1) ended without interruption on heap size).
Trick is that after treshold t next treshold is at least 2^t so the number of phases is small. Each phase takes O(m) ...