Planar strong connectivity helps in parallel depth-first search

Ming Yang Kao*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


This paper proves that for a strongly connected planar directed graph of size n, a depth-first search tree rooted at a specified vertex can be computed in O(log5 n) time with n/log n processors. Previously, for planar directed graphs that may not be strongly connected, the best depth-first search algorithm runs in O(log10 n) time with n processors. Both algorithms run 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)46-62
Number of pages17
JournalSIAM Journal on Computing
Issue number1
StatePublished - 1995

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)


Dive into the research topics of 'Planar strong connectivity helps in parallel depth-first search'. Together they form a unique fingerprint.

Cite this