Tech Report CS-90-16
Parallelism, Preprocessing, and Reachability: A Hybrid Algorithm for Directed Graphs
Philip N. Klein
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 speed-ups, using known methods. We describe a technique allowing significant parallel speed-up even for moderately sparse graphs, following a sequential preprocessing step in which a representation of the graph is created.
(complete text in pdf)