标题:一类树问题的快速并行算法
作者:马绍汉;孙伟;
作者机构:[马绍汉;孙伟] 山东大学计算机科学系,山东大学计算机科学系,
来源:山东大学学报(自然科学版)
出版年:1991
期:01
页码:41-53
关键词:树;有向树;欧拉链技术;并行算法;NC类
摘要:本文给出了一类树问题的快速并行算法.这些问题包括:求树中任意两顶点之间的路径和路径长度、求所有顶点的深度等.以这些基本算法为基础,给出了求树中任意两个顶点的最小公共祖先问题、边修改动态最小生成树问题和树同构问题的并行算法.本文使用的模型是单指令流多数据流共享存贮器并行计算机,允许多个处理机同时读存贮器的一个单元的内容但不允许同时写,称这种模型为CREW PRAM.对n个顶点的树,以上算法均使用O(n)个处理机,时间复杂度为O(logn).按Cook的定义,证明了以上问题都属于NC类.
资源类型:期刊论文
原文链接:http://kns.cnki.net/kns/detail/detail.aspx?FileName=SDDX199101006&DbName=CJFQ1991
TOP