Transitive Reduction in Parallel via Branchings
Phillip B. Gibbons, Richard M. Karp, Vijaya Ramachandran, Danny Soroker, Robert Endre Tarjan · 1988
COSATI COOES 18 SUBJECT TERMS (Corrtnue o n reverse if necessory ond identify by block num ber)directed graphs, graph algorithms, PRAM algorithms, directed spanning trees.We study the following problem: given a strongly connected digraph, find a minimal strongly connected spanning subgraph of it Our mam result is a paralle algorithm for this problem, which runs in polylog parallel time and uses O (n ) pro cessors on a PRAM.Our algorithm is simple and the major tool it uses is comput ing a minimum-weight branching with zero-one weights.We also present sequen tial algorithms for the problem that run in time 0( m +n logn ).22a.