Processor-Efficient Parallel Algorithms for Combinatorial Problems

这项工作的目的是为PRAM模型中的图问题开发快速和处理器高效的并行算法，并在现有的并行机上实现它们，特别注意以下几点。1)无向图上几个问题的高效并行算法，使用了高效的并行搜索技术--开耳分解。2)高效的有向图并行搜索技术，通过开发替代技术来克服这些问题存在的传递闭包瓶颈。3)桶排序的最优并行算法。

This work is aimed at the development of fast and processor efficient parallel algorithms for graph problems in the PRAM model, and at the implementation of them on currently available parallel machines, with particular attention to the following. 1) Efficient parallel algorithms for several problems on undirected graphs using the efficient parallel search technique, open ear decomposition. 2) Efficient parallel search techniques for directed graphs by developing alternative techniques to overcome the transitive closure bottleneck that exists for these problems. 3) An optimal parallel algorithm for bucket sort.