zbMATH — the first resource for mathematics

Transitive compaction in parallel via branchings. (English) Zbl 0718.68058
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.

68R10 Graph theory (including graph drawing) in computer science
68W15 Distributed algorithms
Full Text: DOI