FAW: Parallel Algorithms for Fundamental Graph-Theoretic Problems

FAW：基本图论问题的并行算法

• 批准号: 9023059
• 负责人: Vijaya Ramachandran
• 金额: $ 25万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1991
• 资助国家: 美国
• 起止时间: 1991-11-01 至 1997-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9023059&HistoricalAwards=false
• 关键词: FAW; Parallel; Algorithms; Fundamental; Graph

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.

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