最大权欧几里得生成树

Question

通过运行Kruskal算法（只需更改边函数并首先考虑最大权重边），可以找到最大生成树。我希望找到最大权重欧几里得生成树。是否存在比Kruskal更好的算法（更好的最坏情况运行时间）来找到这样的生成树？

- user1448750

Answer 1

Monma et al.在O(n log h)的时间和O(n)的空间内解决了这个问题，其中n是点数，h是凸包的大小。

该算法（见论文第10页）相当简单，因此即使不完全理解完整的证明也应该可以理解。

- tskuzzy

---

该文档被登录用户锁定。您能概述算法或提供可用版本吗？ - user1448750

当然。我已经附上了算法的截图。 - tskuzzy

这仅适用于二维。我猜这对提问者来说不是问题。 - David Eisenstat

可能提问者想要询问关于http://www.codechef.com/APRIL13/problems/CHEFGAME（高达5D）的解决方案。我将在4月15日之后回答此问题。 - Kavish Dwivedi