Gibbons, Phillip; Karp, Richard; Ramachandran, Vijaya; Soroker, Danny; Tarjan, Robert Transitive compaction in parallel via branchings. (English) Zbl 0718.68058 J. Algorithms 12, No. 1, 110-125 (1991). The transitive compaction problem for strongly connected digraphs is: given a strongly connected digraph G, find a strongly connected spanning subgraph for which the removal of any arc destroys strong connectivity. A parallel algorithm for this problem is presented. It runs in time \(0(\log^ 4n)\) and uses \(0(n^ 3)\) processors on a CREW PRAM. The major tool used by the algorithm is computing a minimum-weight branching with zero-one weights. Two sequential algorithms for the problem that run in time \(0(m+n \log n)\) are also presented. Reviewer: M.Zimand (Bucureşti) Cited in 3 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 68W15 Distributed algorithms Keywords:strongly connected digraphs; CREW PRAM PDFBibTeX XMLCite \textit{P. Gibbons} et al., J. Algorithms 12, No. 1, 110--125 (1991; Zbl 0718.68058) Full Text: DOI