Processor-Efficient Parallel Algorithms for Combinatorial Problems

点击翻译按钮获取中文摘要

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.