A Divide-and-conquer Algorithm for Identifying Strongly Connected Components ?
A Divide-and-conquer Algorithm for Identifying Strongly Connected Components ?
复制标题
用于识别强连通分量的分而治之算法？
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Ali Pinar
中科院分区：
文献类型：
--
作者：
D. Coppersmith;L. Fleischer;B. Hendrickson;Ali Pinar
基于深度优先搜索的算法可以在最优线性时间内找到有向图的强连通分支。不幸的是，深度优先搜索很难并行化。我们描述了解决该问题的两种分治算法，它们具有更大的并行化潜力。我们表明，我们的简单算法的预期串行运行时间为O（m log n），为n个顶点和m边的图。然后，我们证明了第二个算法有O（mlog n）最坏情况下的复杂性。
Strongly connected components of a directed graph can be found in an optimal linear time, by algorithms based on depth first search. Unfortunately, depth first search is difficult to parallelize. We describe two divide--and--conquer algorithms for this problem that have significantly greater potential for parallelization. We show the expected serial runtime of our simpler algorithm to be O(m log n), for a graph with n vertices and m edges. We then show that the second algorithm has O(mlog n) worst--case complexity.