Parallel algorithms for distributed systems and software engineering.

摘要

Networks, database systems, computer processes and programs are often presented by graphs. Parallel methods for solving graph problems provide the means of parallel processing for distributed systems and software engineering.; In this dissertation we present a new parallel technique for graph decomposition, pruning decomposition, which partitions a graph into certain disjoint structures. Using the pruning decomposition, we introduce the efficient methods for computing st-numbering, finding biconnected components and ear decomposition on the EREW P-RAM model of computation.; Based on these results, we give some efficient parallel algorithms for other problems such as vertex location trees, strong orientation, and minimum cutset on reducible graphs.