Author |
Topic: Minimum Spanning tree (Read 1147 times) |
|
The_Hawk
Newbie
Posts: 1
|
 |
Minimum Spanning tree
« on: Apr 2nd, 2009, 9:39am » |
 Quote  Modify
|
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) ?
|
|
 IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender: 
Posts: 919
|
|
Re: Minimum Spanning tree
« Reply #1 on: Apr 2nd, 2009, 10:11am » |
Quote Modify
|
You don't have time to read entire input.
|
|
IP Logged |
|
|
|
nks
Junior Member
Gender:
Posts: 145
|
|
Re: Minimum Spanning tree
« Reply #2 on: Apr 2nd, 2009, 11:53pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Minimum Spanning tree
« Reply #3 on: Apr 3rd, 2009, 12:07am » |
Quote Modify
|
on Apr 2nd, 2009, 11:53pm, nks wrote:| Do these alogs not work in O(n log*n) ? |
|
Not if you include reading the input, which is O(n2) in the number of vertices.
And it depends on the datastructure as well. e.g. Prim's algorithm isn't O(n log n) if the graph is represented as a adjacency matrix or fibonacci heap + adjacency list.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Minimum Spanning tree
« Reply #4 on: Apr 3rd, 2009, 6:54am » |
Quote Modify
|
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).
|
| « Last Edit: Apr 3rd, 2009, 6:56am by Hippo » |
IP Logged |
|
|
|
nakli
Junior Member
Gender:
Posts: 62
|
|
Re: Minimum Spanning tree
« Reply #5 on: Jul 30th, 2010, 12:00am » |
Quote Modify
|
A paper here 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 - 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 ?
|
|
IP Logged |
I was born naked on a bed with a lady.
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Minimum Spanning tree
« Reply #6 on: Aug 7th, 2010, 4:31pm » |
Quote Modify
|
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) ...
|
| « Last Edit: Aug 7th, 2010, 4:39pm by Hippo » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print