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

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

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.