Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs

Ming Yang Kao*, Philip N. Klein

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

There are linear-time sequential algorithms for many fundamental problems related to digraph reachability. In contrast, the best parallel algorithms known for these problems, although fast, require a great many processors and, hence, require much more computation overall than the sequential algorithms. This contrast reflects a seemingly unavoidable reliance on transitive closure techniques in parallel algorithms for digraph reachability. To further understanding of the nature of the bottleneck, we present a collection of polylog-time reductions among reachability problems. These reductions use only linear processors and work for general graphs. Futhermore, for planar digraphs, we give polylog-time algorithms for the following problems: (1) directed ear decomposition, (2) topological ordering, (3) digraph reachability, (4) descendant counting, and (5) depth-first search. Our new algorithms use only a linear number of processors, and, hence, are the first to be within a polylog factor of optimal in their use of parallelism.

Original languageEnglish (US)
Pages (from-to)459-500
Number of pages42
JournalJournal of Computer and System Sciences
Volume47
Issue number3
DOIs
StatePublished - 1993

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs'. Together they form a unique fingerprint.

Cite this