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.