Parallelization Of Graph Algorithms

The notions of tree decomposition and treewidth play important roles in felds ofgraph theory, algorithms, and parameterized complexity research. For one main rea-son, using tree decomposition, many intractable problems on Graph (NP-hard) becomelinear or polynomial solvable when the graphs have a bounded treewidth. The applica-tion of tree decomposition also promotes the research of programming analysis theoryand social network analysis.Many problems on graph, like vertex coloring, graph optimization (minimal ver-tex cover, maximal weighted independent set), can be solved using tree decompositionby a bottom-up dynamic recursive algorithms, in which, the computation of node re-lies all the results of its children. So far, the parallel programming for this kind ofalgorithms is to execute the computation of the children node in parallel. However,when the shape tree decomposition is ill-balanced or is narrow and deep, the perfor-mance of parallel program will be very inefcient. Moreover, the bottom-up dynamicprogramming is hard to apply in scalable distributed systems.We have surveyed diferent techniques of tree parallelism, and one importan-t achievement is the application of the Third Homomorphism Theorem, which can notonly declaim the existent but also the deriving method of a parallel algorithm from atwo-wards solved program. The tree parallelism is based on zipper structure, which isalistofelementsofsubtreeleftafteraup-bottomwalkalongthetree. Thecomputationamong subtrees can be executed in parallel, and moreover, in distributed systems.The key point to solve graph problem via tree decomposition is using dynamicprogramming to manage the information among nodes. In order to parallelize graphalgorithms correctly and efciently, the most important things to is how to design aconsistent and efcient algorithm to merge the results of subtrees.The main contribution of my thesis can be summarized as the following aspects: Transform a graph into zipper structure, which provides data structure for paral-lelization of graph algorithms.Extend the application of the Third Homomorphism Theorem to tree decompo-sition, and introduce how to transform a bottom-up algorithm into a parallel one.Present the parallelization of some important graph problems.Design a systemic framework of algorithms transformation, which can computesome graph problems in parallel.