Transitive compaction in parallel via branchings

Phillip Gibbons, Richard Karp, Vijaya Ramachandran, Danny Soroker, Robert Tarjan

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


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

Original languageEnglish (US)
Pages (from-to)110-125
Number of pages16
JournalJournal of Algorithms
Issue number1
StatePublished - Mar 1991

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics


Dive into the research topics of 'Transitive compaction in parallel via branchings'. Together they form a unique fingerprint.

Cite this