External Memory Algorithms for Diameter and All-Pairs Shortest-Paths on Sparse Graphs
External Memory Algorithms for Diameter and All-Pairs Shortest-Paths on Sparse Graphs
复制标题
稀疏图上直径和全对最短路径的外部记忆算法
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Laura Toma
中科院分区：
文献类型：
--
作者：
L. Arge;U. Meyer;Laura Toma
我们开发了直径和所有对最短路径(APSP)的I/O高效算法。对于边权非负且E/V=o(B/logV)的一般无向图G(V，E)，我们的方法是第一个获得o(V2)I/O的方法。对于无权无向图，仅需(O(V CDOT Extrm{Sort}(E)个I/O即可解决APSP问题。我们的加权方法和未加权方法都需要O(V2)空间。对于直径计算，我们提供了I/O空间权衡。最后，我们给出了有向平面图的直径计算和APSP计算的改进结果。
We develop I/O-efficient algorithms for diameter and all-pairs shortest-paths (APSP). For general undirected graphs G(V,E) with non-negative edge weights and E/V = o(B/ log V) our approaches are the first to achieve o(V 2) I/Os. We also show that for unweighted undirected graphs, APSP can be solved with just (O(V cdot extrm{sort}(E))) I/Os. Both our weighted and unweighted approaches require O(V 2) space. For diameter computations we provide I/O-space tradeoffs. Finally, we provide improved results for both diameter and APSP computation on directed planar graphs.