树分解与树宽概念的提出在图论、算法和参数复杂性等领域有重要的意义。其中一个主要原因是利用树分解,原来许多在图上困难的问题(如NP难),在对某类树宽是固定参数的图上,可以得到一个参数复杂性是线性或者多项式的算法。树分解技术在程序分析理论,社交网络分析等研究领域也起到重要作用。　　基于图数据结构的问题,比如图最优化问题(最小顶点覆盖问题,最大权值独立集问题),图k可染色问题,图同构问题等等在树分解上通常是使用一个自底向上的动态规划算法,即父节点值的计算依赖与其所有子节点的值。目前这类算法的并行化操作是针对子节点的值可以独立并行计算。但是,当树分解的形状具有很差的平衡性,或者是一棵深而窄的树,那么,并行效果将会很不理想。更重要的是,对于大规模数据,自底向上的算法不适合分布式的计算模型。　　对树数据结构上的算法并行化,相关领域已经有相对成熟的成果。其中之一是利用第三同态定理在树上的应用,即是如果提供计算一问题的一个自顶向下和一个自底向上的串行算法,那么就存在一个解决该问题的并行算法。第三同态定理的树上的应用是基于zipper的数据结构,其是把树沿着一条从根结点到叶子的路径切割而成的子树序列。子树间的计算可以高度并行化,并且可以分布到远程的机器上并行计算。　　利用树分解计算图上最优化类问题一个关键技术是利用动态规划自顶向上地管理子树的信息。平衡切割树分解,设计一致且高效的合并子树信息的算法,是正确高效实现图最优化问题算法并行化的保证。　　本论文工作的主要贡献由如下几方面组成:　　1.结合树分解和切割树的技术,提出了存储图的列表数据结构,为图算法的并行化提供数据结构上的支持。　　2.利用第三同态定理在树分解上的拓广,提出从自底向上的算法转化为并行算法的方法。　　3.给出一些重要的图上问题的并行计算方法。　　4.设计系统的算法转换框架,自动并行化图上一类问题的算法。