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

Ming Yang Kao; Philip N. Klein

doi:10.1145/100216.100237

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

Ming Yang Kao^*, Philip N. Klein

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Proc 22nd Annu ACM Symp Theory Comput
Publisher	Publ by ACM
Pages	181-192
Number of pages	12
ISBN (Print)	0897913612, 9780897913614
DOIs	https://doi.org/10.1145/100216.100237
State	Published - 1990
Event	Proceedings of the 22nd Annual ACM Symposium on Theory of Computing - Baltimore, MD, USA Duration: May 14 1990 → May 16 1990

Publication series

Name	Proc 22nd Annu ACM Symp Theory Comput

Other

Other	Proceedings of the 22nd Annual ACM Symposium on Theory of Computing
City	Baltimore, MD, USA
Period	5/14/90 → 5/16/90

ASJC Scopus subject areas

Engineering(all)

Access to Document

10.1145/100216.100237

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

@inproceedings{740f4268379d4a28aaeb5572b4fa0795,

title = "Towards overcoming the transitive-closure bottleneck. Efficient parallel algorithms for planar digraphs",

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.",

author = "Kao, {Ming Yang} and Klein, {Philip N.}",

note = "Funding Information: * Research supported in part by NSF Grant CCR-8909323. + Research supported in part by ONR Grant NOOO14-88-K-0243 and DARPA Grant NOtXl39-88-C0113. Most of this work was done while he was at Aiken Computation Laboratory, Harvard University.; Proceedings of the 22nd Annual ACM Symposium on Theory of Computing ; Conference date: 14-05-1990 Through 16-05-1990",

year = "1990",

doi = "10.1145/100216.100237",

language = "English (US)",

isbn = "0897913612",

series = "Proc 22nd Annu ACM Symp Theory Comput",

publisher = "Publ by ACM",

pages = "181--192",

booktitle = "Proc 22nd Annu ACM Symp Theory Comput",

}

Kao, MY & Klein, PN 1990, Towards overcoming the transitive-closure bottleneck. Efficient parallel algorithms for planar digraphs. in Proc 22nd Annu ACM Symp Theory Comput. Proc 22nd Annu ACM Symp Theory Comput, Publ by ACM, pp. 181-192, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, 5/14/90. https://doi.org/10.1145/100216.100237

TY - GEN

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

AU - Kao, Ming Yang

AU - Klein, Philip N.

N1 - Funding Information: * Research supported in part by NSF Grant CCR-8909323. + Research supported in part by ONR Grant NOOO14-88-K-0243 and DARPA Grant NOtXl39-88-C0113. Most of this work was done while he was at Aiken Computation Laboratory, Harvard University.

PY - 1990

Y1 - 1990

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0025149855&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025149855&partnerID=8YFLogxK

U2 - 10.1145/100216.100237

DO - 10.1145/100216.100237

M3 - Conference contribution

AN - SCOPUS:0025149855

SN - 0897913612

SN - 9780897913614

T3 - Proc 22nd Annu ACM Symp Theory Comput

SP - 181

EP - 192

BT - Proc 22nd Annu ACM Symp Theory Comput

PB - Publ by ACM

T2 - Proceedings of the 22nd Annual ACM Symposium on Theory of Computing

Y2 - 14 May 1990 through 16 May 1990

ER -