TY - JOUR
T1 - Transitive compaction in parallel via branchings
AU - Gibbons, Phillip
AU - Karp, Richard
AU - Ramachandran, Vijaya
AU - Soroker, Danny
AU - Tarjan, Robert
N1 - Funding Information:
*Supported in part by the International Computer Science Institute, Berkeley, California. ‘Also supported by NSF Grant CCR-84119.54. Current affiliation: University of California at Berkeley and International Computer Science Institute, Berkeley, CA. *Also supported by Joint Services Electronics Program under NOO014-84-C-0149. Current affiliation: Department of Computer Sciences, The University of Texas at Austin, Austin, TX 78712. “Research at Princeton University partially supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center grant NSF-STCSS-09648, and NSF Grant CCR-8920505. Current affiliation: Princeton University and NEC Research Institute, Princeton, NJ. ‘Current affiliation: AT & T Bell Laboratories, Murray Hill, NJ 07974. ‘Current affiliation: Shell Development Company, PO Box 481, Houston, TX 77011.
PY - 1991/3
Y1 - 1991/3
N2 - We study the following problem: given a strongly connected digraph, find a minimal strongly connected spanning subgraph of it. Our main result is a parallel algorithm for this problem, which runs in polylog parallel time and uses O(n3) processors on a PRAM. Our algorithm is simple and the major tool it uses is computing a minimum-weight branching with zero-one weights. We also present sequential algorithms for the problem that run in time O(m + n · log n).
AB - We study the following problem: given a strongly connected digraph, find a minimal strongly connected spanning subgraph of it. Our main result is a parallel algorithm for this problem, which runs in polylog parallel time and uses O(n3) processors on a PRAM. Our algorithm is simple and the major tool it uses is computing a minimum-weight branching with zero-one weights. We also present sequential algorithms for the problem that run in time O(m + n · log n).
UR - http://www.scopus.com/inward/record.url?scp=0037814181&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0037814181&partnerID=8YFLogxK
U2 - 10.1016/0196-6774(91)90026-U
DO - 10.1016/0196-6774(91)90026-U
M3 - Article
AN - SCOPUS:0037814181
SN - 0196-6774
VL - 12
SP - 110
EP - 125
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 1
ER -