A maximum spanning tree can be found by running kruskal's algorithm(just changing the edges function and considering the max weight edges first). I am interested in finding the max weight euclidean spanning tree. Does there exist a better algorithm(better worst case running time) than kruskal's to find such a spanning tree?
Asked
Active
Viewed 737 times
1 Answers
3
Monma et al. solve this in O(n log h) time and O(n) space, where n is the number of points and h is the size of the convex hull.
The algorithm (p.10 of the paper) is fairly simple so it should be accessible even without understanding the full proof.
tskuzzy
- 35,812
- 14
- 73
- 140
-
1the document is locked by a sign in. Can you outline the algorithm or make it available... – Apr 11 '13 at 04:09
-
Sure. I have attached a screenshot of the algorithm. – tskuzzy Apr 11 '13 at 04:41
-
(This is for two dimensions only. I guess that's not a problem for the asker.) – David Eisenstat Apr 11 '13 at 13:51
-
probably asker wants to ask solution for http://www.codechef.com/APRIL13/problems/CHEFGAME (upto 5D). I would only answer this after 15th april – Kavish Dwivedi Apr 11 '13 at 17:09