I/O-Efficient Algorithms for Topological Sort and Related Problems
I/O-Efficient Algorithms for Topological Sort and Related Problems
复制标题
拓扑排序及相关问题的 I/O 高效算法
DOI：
10.1137/1.9781611975482.124
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Yang, Eugene
中科院分区：
文献类型：
--
作者：
Cao, Nairen;Fineman, Jeremy T;Russell, Katina;Yang, Eugene
本文给出了对有向无环图进行拓扑排序的I/O高效算法，以及对有向图G=(V，E)的强连通分支进行识别和拓扑排序的更一般问题。这两种算法都是随机化的，并且具有I/O开销O(Sort(E)·poly(Log V))，概率很高，其中ort(E)=O(E/BlogM/B(E/B))是在具有SIZE-BLOCK和SIZE-MCACHE/内存的机器上对|E|元素数组进行排序的I/O开销。这是解决这些问题的第一个算法，每个顶点不会产生至少一个I/O，因此，这些算法是第一个针对稀疏图的I/O高效算法。通过应用时间向前处理技术，这些算法还为有向无环图上的大多数问题(如最短路径)以及任意有向图上的单源可达性问题提供了I/O高效的算法。
This article presents I/O-efficient algorithms for topologically sorting a directed acyclic graph and for the more general problem identifying and topologically sorting the strongly connected components of a directed graphG= (V, E). Both algorithms are randomized and have I/O-costsO(sort(E) · poly(log V)), with high probability, wheresort(E) = O(E/BlogM/B(E/B)) is the I/O cost of sorting an |E|-element array on a machine with size-Bblocks and size-Mcache/internal memory. These are the first algorithms for these problems that do not incur at least one I/O per vertex, and as such these are the first I/O-efficient algorithms for sparse graphs. By applying the technique of time-forward processing, these algorithms also imply I/O-efficient algorithms for most problems on directed acyclic graphs, such as shortest paths, as well as the single-source reachability problem on arbitrary directed graphs.
登录
查看更多内容
DOI：
--
发表时间：
2013
期刊：
arXiv.org
影响因子：
--
作者：
E. Cohen;A. Fiat;Haim Kaplan;L. Roditty
通讯作者：
L. Roditty
稀疏图上直径和全对最短路径的外部记忆算法
DOI：
--
发表时间：
2004
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
L. Arge;U. Meyer;Laura Toma
通讯作者：
Laura Toma
DOI：
--
发表时间：
2011
期刊：
Workshop on Algorithm Engineering and Experimentation
影响因子：
--
作者：
Deepak Ajwani;Adan Cosgaya;N. Zeh
通讯作者：
N. Zeh
无向图中的外部存储器精确和近似全对最短路径
DOI：
--
发表时间：
2005
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
R. Chowdhury;V. Ramachandran
通讯作者：
V. Ramachandran
DOI：
--
发表时间：
2003
期刊：
影响因子：
--
作者：
D. Coppersmith;L. Fleischer;B. Hendrickson;Ali Pinar
通讯作者：
Ali Pinar