| 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. |
