Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Report ID:

TR-171-88

Authors:

Gibbons, Phillip [1] / Karp, Richard M. [2] / Ramachandran, Vijaya [3] / Soroker, Danny [4] / Tarjan, Robert E. [5]

Date:

June 1988

Pages:

17

Download Formats:

[PDF [6]]

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-weigh branching with zero-one weights. We also present sequential algorithms for the problem that run in time (m+ n * log n).

**Links**

[1] http://www.cs.princeton.edu/research/techreps/author/674

[2] http://www.cs.princeton.edu/research/techreps/author/94

[3] http://www.cs.princeton.edu/research/techreps/author/167

[4] http://www.cs.princeton.edu/research/techreps/author/722

[5] http://www.cs.princeton.edu/research/techreps/author/384

[6] ftp://ftp.cs.princeton.edu/techreports/1988/171.pdf