External-memory exact and approximate all-pairs shortest-paths in undirected graphs
External-memory exact and approximate all-pairs shortest-paths in undirected graphs
复制标题
无向图中的外部存储器精确和近似全对最短路径
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
V. Ramachandran
中科院分区：
文献类型：
--
作者：
R. Chowdhury;V. Ramachandran
我们提出了几种新的外部存储器算法，用于查找 <i>V</i> 节点中的所有对最短路径。 <i>E</i>边无向图。对于未加权无向图中的所有对最短路径和直径，我们提出了具有 <i>O(V·E/B</i> log <i>M/B E/B)</i> I/O 的缓存忽略算法，其中 <i>B</i> 是块大小，<i>M</i> 是内部存储器的大小。对于加权无向图，我们提出了一种缓存感知 APSP 算法，该算法执行 <i>O</i>(<i>V</i>·(√VE/B+E/B log E/B)) I/O。我们还提出了高效的缓存感知算法，可以找到未加权图中所有顶点对之间的路径，其长度在最短路径长度的小加性常数内。我们所有的结果都改进了已知的这些问题的早期结果。对于近似 APSP，我们提供了第一个重要的结果。我们的直径结果使用 <i>O(V + E)</i> 额外空间，而我们所有其他算法都使用 <i>O</i>(V<sup>2</sup>) 空间。
We present several new external-memory algorithms for finding all-pairs shortest paths in a <i>V</i>-node. <i>E</i>-edge undirected graph. For all-pairs shortest paths and diameter in unweighted undirected graphs we present cache-oblivious algorithms with <i>O(V·E/B</i> log <i>M/B E/B)</i> I/Os, where <i>B</i> is the block-size and <i>M</i> is the size of internal memory. For weighted undirected graphs we present a cache-aware APSP algorithm that performs <i>O</i>(<i>V</i>·(√VE/B+E/B log E/B)) I/Os. We also present efficient cache-aware algorithms that find paths between all pairs of vertices in an unweighted graph with lengths within a small additive constant of the shortest path length.All of our results improve earlier results known for these problems. For approximate APSP we provide the first nontrivial results. Our diameter result uses <i>O(V + E)</i> extra space, and all of our other algorithms use <i>O</i>(V<sup>2</sup>) space.