FAW: Parallel Algorithms for Fundamental Graph-Theoretic Problems

本研究将集中在图论问题并行算法设计的基本问题。将开发以下问题的并行算法：o有向图的基本问题，以及传递闭包瓶颈的消除。o最大匹配问题、最大流量问题和阻塞流问题。o增量问题。在这些问题中，给定了具有某些属性的输入图，但这些属性可能会由于添加或删除边或顶点而改变。这些问题在动态变化的网络评价中具有重要意义。o桶排序。这是当输入被限制为多项式大小的整数时的排序问题。虽然这不是一个图问题，但它在大多数图算法中作为子例程出现，并且通常是其效率的限制因素。这些新算法将在共享内存PRAM模型中开发，并将考虑它们在其他标准并行计算模型上的实现。从这些新的并行算法中发展出新的改进的顺序算法。

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.