## 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(log^{3} 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 language | English (US) |
---|---|

Pages (from-to) | 431-459 |

Number of pages | 29 |

Journal | SIAM Journal on Computing |

Volume | 22 |

Issue number | 3 |

DOIs | |

State | Published - Jan 1 1993 |

## ASJC Scopus subject areas

- General Computer Science
- General Mathematics