度量空间中的高效最小生成树

Question

我在一些度量空间中有一大组点(数量n> 10000)(例如配备Jaccard距离).我想用最小的生成树连接它们,使用公制作为边缘的权重.

• 是否存在运行时间小于O(n ²)的算法？
• 如果没有,是否存在运行时间小于O(n ²)的算法(可能使用随机化)？
• 如果没有,是否有一个算法在小于O(n ²)的时间内运行并且给出了最小生成树的良好近似值？
• 如果没有,是否有这样的算法不存在的原因？

先感谢您!

编辑下面的海报: 查找最小生成树的经典算法在这里不起作用.他们的运行时间有一个E因子,但在我的情况下E = n ^2,因为我实际上考虑了完整的图表.我也没有足够的内存来存储所有> 49995000个可能的边缘.

Answer 1

显然,根据这个:估计次线性时间内度量最小生成树的权重没有确定性o(n ^ 2)(注意:smallOh,这可能是你的意思,小于O(n ^ 2),我想)算法.该论文还给出了度量最小权重生成树的子线性随机算法.

另请参阅本文:一种最优的最小生成树算法,它提供了一种最优算法.该论文还声称,最优算法的复杂性尚不清楚!

第一篇论文中的参考文献应该是有用的,而且该论文可能与您的问题最相关.

希望有所帮助.