Parallelism, Preprocessing, and Reachability: A Hybrid Algorithm for Directed Graphs

✍ Scribed by P.N. Klein

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 602 KB
• Volume: 14
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1993.1017

✦ Synopsis

The problem of reachability in a directed graph has resisted attempts at efficient parallelization. Only for fairly dense graphs can we efficiently achieve significant parallel speedups, using known methods. We describe a technique allowing significant parallel speedup even for moderately sparse graphs, following a sequential preprocessing step in which a representation of the graph is created. 199.3 Academic Press, Inc.