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

Ming Yang Kao*

*Corresponding author for this work

Research output: Contribution to journalArticle

8 Scopus citations

Abstract

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
Volume22
Issue number3
DOIs
StatePublished - Jan 1 1993

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint 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