Fast and Processor-Efficient Parallel Algorithms for Reducible Flow Graphs

摘要

This document presents parallel NC algorithms for recognizing reducible flow graphs (rfg's), 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 processors 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. It is shown that finding a minimum feedback vertex in vertex-weighted rfg's or finding a minimum feedback arc set in arc-weighted rfg's is complete. For arc or vertex weights in unary, we present 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. Keywords: Parallel computations. (KR)