• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Proceedings of the 25th ACM symposium on parallelism in algorithms and architectures >Parallel Graph Decompositions Using Random Shifts
【24h】

Parallel Graph Decompositions Using Random Shifts

机译：使用随机移位的并行图分解

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

摘要

We show an improved parallel algorithm for decomposing an undirected unweighted graph into small diameter pieces with a small fraction of the edges in between. These decompositions form critical subroutines in a number of graph algorithms. Our algorithm builds upon the shifted shortest path approach introduced in [Blelloch,Gupta,Koutis,Miller,Peng, Tangwongsan, SPAA 2011]. By combining various stages of the previous algorithm, we obtain a significantly simpler algorithm with the same asymptotic guarantees as the best sequential algorithm.
机译：我们展示了一种改进的并行算法，用于将无向未加权图分解为小直径的块，并且它们之间的边缘很小。这些分解在许多图算法中形成了关键子程序。我们的算法基于[Blelloch，Gupta，Koutis，Miller，Peng，Tangwongsan，SPAA 2011]中引入的移动最短路径方法。通过组合先前算法的各个阶段，我们获得了一种与最佳顺序算法相同且渐近保证的明显简化的算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号