A divide-and-conquer algorithm for identifying strongly connectedcomponents

Coppersmith, Don ; Fleischer, Lisa ; Hendrickson, Bruce ; Pinar, Ali

Lawrence Berkeley National Laboratory

关键词: Data Analysis;    Design And Analysis Of Algorithms Graph Algorithms Parallelalgorithms Strongly Connected Components Divide--And--Conquer Discreteordinates Method;    99 General And Miscellaneous//Mathematics, Computing, And Information Science;    Algorithms;    Computer Calculations Design And Analysis Of Algorithms Graph Algorithms Parallelalgorithms Strongly Connected Components Divide--And--Conquer Discreteordinates Method;   

DOI  :  10.2172/889876
RP-ID  :  LBNL--51867
RP-ID  :  DE-AC02-05CH11231
RP-ID  :  889876

美国|英语

来源: UNT Digital Library

【 摘 要 】

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.