Tech Report CS-90-16

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

Philip N. Klein

July 1990


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)