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: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

Currently, there is a significant gap between the best sequential and parallel complexities of many fundamental problems related to digraph reachability. This complexity bottleneck essentially reflects a seemingly unavoidable reliance on transitive closure techiques in parallel algorithms for digraph reachability. To pinpoint the nature of the bottleneck, we develop a collection of polylog-time reductions among reachability problems. These reductions use only linear processors and work for general graphs. Furthermore, for planar digraphs, we give polylog-time algorithms for the following problems: (1) directed ear decomposition, (2) topological ordering, (3) digraph reachability, (4) descendent counting, and (5) depth-first search. These algorithms use only linear processors and therefore reduce the complexity to within a polylog factor of optimal.

Original languageEnglish (US)
Title of host publicationProc 22nd Annu ACM Symp Theory Comput
PublisherPubl by ACM
Pages181-192
Number of pages12
ISBN (Print)0897913612, 9780897913614
DOIs
StatePublished - 1990
EventProceedings of the 22nd Annual ACM Symposium on Theory of Computing - Baltimore, MD, USA
Duration: May 14 1990May 16 1990

Publication series

NameProc 22nd Annu ACM Symp Theory Comput

Other

OtherProceedings of the 22nd Annual ACM Symposium on Theory of Computing
CityBaltimore, MD, USA
Period5/14/905/16/90

ASJC Scopus subject areas

  • Engineering(all)

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