Fast and Processor-Efficient Parallel Algorithms for Reducible Flow Graphs
Vijaya Ramachandran · 1988
NOTATION 17. COSATI COOES 18. SUBJECT TERMS (Contìnua o n cavano if nacassary and identify by block number) algorithms, directed graphs, flow graphs, parallel computation, PRAM model.We present parallel NC algorithms for recognizing reducible flow graphs, and for finding dominators, minimum feedback vertex sets, and a depth first search numbering in an rfg.All of these algorithms run in polylog parallel time using M(n) processors, where M(n) is the number of proces sors needed to multiply two nxn matrices in polylog time; this is the best processor bound currently known for polylog-time parallel algorithms for directed graphs.We show that finding a minimum feedback vertex set in vertex-weighted rfg's or finding a minimum feedback arc set in arc-weighted rfg's is P-complete.For arc or vertex weights in unary, we présent RNC algorithms for these problems and show that these problems are in NC if and only if the problem of finding a maximum matching is in NC.22a.