FAW: Parallel Algorithms for Fundamental Graph-Theoretic Problems

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

This research will focus on fundamental issues in parallel algorithm design for graph-theoretic problems. Parallel algorithms for the following problems will be developed: o Basic problems on directed graphs, and the elimination of the transitive closure bottleneck. o The maximum matching problem, the maximum flow problem, and the blocking flow problem. o Incremental problems. These are problems in which an input graph with certain properties is given, but these properties may change due to the addition or deletion of an edge or vertex. These problems are of importance in the evaluation of a dynamically changing network. o Bucket sort. This is the sorting problem when the inputs are restricted to be integers of polynomial size. While this is not a graph problem, it occurs as a subroutine in most graph algorithms, and is often the limiting factor in their efficiency. These new algorithms will be developed in the shared-memory PRAM model and their implementations on other standard models of parallel computation will be considered. The development of new improved sequential algorithms from these new parallel algorithms will be investigated.