# 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.

##### MSC:
 68R10 Graph theory (including graph drawing) in computer science 68W15 Distributed algorithms
##### Keywords:
strongly connected digraphs; CREW PRAM
Full Text: