Linear-processor NC algorithms for planar directed graphs I: Strongly connected components

Ming Yang Kao*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


Finding strongly connected components in a fundamental step in many algorithms for directed graphs. In sequential computation this problem has an optimal linear-time algorithm. In parallel computation, however, it remains an open problem whether polylogarithmic time and a linear number of processors are sufficient for computing the strongly connected components on a parallel random-access machine. This paper provides the first nontrivial partial solution to the open problem: for a planar directed graph of size n the strongly connected components can be computed deterministically in O(log3 n) time with n/log n processors. The algorithm runs on a parallel random-access machine that allows concurrent reads and concurrent writes in its shared memory and, in case of a write conflict, permits an arbitrary processor to succeed.

Original languageEnglish (US)
Pages (from-to)431-459
Number of pages29
JournalSIAM Journal on Computing
Issue number3
StatePublished - Jan 1 1993

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Linear-processor NC algorithms for planar directed graphs I: Strongly connected components'. Together they form a unique fingerprint.

Cite this