• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Experimental algorithms >Geometric Minimum Spanning Trees with GeoFilterKruskal
【24h】

Geometric Minimum Spanning Trees with GeoFilterKruskal

机译：使用GeoFilterKruskal的几何最小生成树

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Let P be a set of points in R~d. We propose GeoFilterKruskal, an algorithm that computes the minimum spanning tree of P using well separated pair decomposition in combination with a simple modification of Kruskal's algorithm. When P is sampled from uniform random distribution, we show that our algorithm takes one parallel sort plus a linear number of additional steps, with high probability, to compute the minimum spanning tree. Experiments show that our algorithm works better in practice for most data distributions compared to the current state of the art [31]. Our algorithm is easy to parallelize and to our knowledge, is currently the best practical algorithm on multi-core machines for d > 2.
机译：令P为R〜d中的一组点。我们提出了GeoFilterKruskal，这是一种使用分离良好的对分解并结合Kruskal算法的简单修改来计算P的最小生成树的算法。当从均匀随机分布中采样P时，我们证明了我们的算法采用一种并行排序加上线性附加步骤数（很有可能）来计算最小生成树。实验表明，与当前的最新技术相比，我们的算法在大多数数据分布上的实践效果更好[31]。我们的算法易于并行化，据我们所知，对于d> 2，当前是多核计算机上最佳的实用算法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号