一类树问题的快速并行算法

FAST PARALLEL ALGORITHMS FOR A CLASS OF TREE PROBLEMS

本文给出了一类树问题的快速并行算法.这些问题包括:求树中任意两顶点之间的路径和路径长度、求所有顶点的深度等.以这些基本算法为基础,给出了求树中任意两个顶点的最小公共祖先问题、边修改动态最小生成树问题和树同构问题的并行算法.本文使用的模型是单指令流多数据流共享存贮器并行计算机,允许多个处理机同时读存贮器的一个单元的内容但不允许同时写,称这种模型为CREW PRAM.对n个顶点的树,以上算法均使用O(n)个处理机,时间复杂度为O(logn).按Cook的定义,证明了以上问题都属于NC类.

This paper presents some fast parallel algorithms for a class of tree problems. These problems include finding the path and the path length between two vertices in a tree, computing the depth of all vertices in a tree and etc. Based on these foundamental algorithms, this paper describe parallel algorithms for problem of finding the least commom ancestor of two vertices in a tree, for edge updating dynamic minimum spanning tree problem and tree isormophism problem. The model for parallel computation we used is single-instruction stream mutiple-data stream shared memory computer, allowing concurrent read but only exclusive write, which is known as CREW PRAM. All these algorithms run in O(logn) time using O(n) processors, where n is the number of vertices in the tree. So according to the definition of Cook, we show these problems lie in the class NC.