Towards Overcoming the Transitive-Closure Bottleneck: Efficient Parallel Algorithms for Directed Graphs

在使用并行随机存取机的并行计算中， 一些有效的算法是已知的问题，涉及定向 图表。 最能说明这种情况的例子是 有向图可达性问题。 在其最简单的形式中， 问题是测试图是否包含从 给另一个顶点。 的最佳顺序算法 问题使用简单的图搜索并在最佳线性时间内运行。 在 相比之下，对于同一问题， 计算给定图的传递闭包，并使用 处理器的超线性数量。 因此，有一个重要的 最佳顺序和最佳并行之间的差距 问题的复杂性。 这种对传递闭包的依赖 技术和由此产生的低效率也存在于最好的 已知的并行算法用于许多其它基本问题， 有向图论 这个项目的目标是消除复杂性瓶颈 由于这种对传递性的不期望的依赖 关闭技术。 对于有向图的基本问题， 并行算法将被设计成在多对数时间内运行 并且仅使用线性数量的处理器，因此，实现了 最佳的复杂度内的一个polylogarithmetic因子。

In parallel computation using parallel random access machines, very few efficient algorithms are known for problems involving directed graphs. The most demonstrative example of this situation is the problem of directed graph reachability. In its simplest form, the problem is to test whether a graph contains a directed path from a given vertex to another. The best sequential algorithms for the problem use simple graph searches and run in optimal linear time. In contrast, the best known parallel algorithm for the same problem computes the transitive closure of the given graph, and uses a superlinear number of processors. Therefore, there is a significant gap between the optimal sequential and the best known parallel complexities of the problem. This reliance on transitive closure techniques and the resulting inefficiency are also present in the best known parallel algorithms for many other fundamental problems in directed graph theory. The goal of this project is to remove the complexity bottleneck resulting from this undesirable reliance on transitive closure techniques. For fundamental problems on directed graphs, parallel algorithms will be designed that run in polylogarithmic time and use only a linear number of processors, and therefore, achieve an optimal complexity within a polylogarithmic factor.