权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

克服传递闭包瓶颈：有向图的高效并行算法

基本信息

批准号：
9101385
负责人：
Ming-Yang Kao
金额：
$ 5.66万
依托单位：
Duke University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
1991
资助国家：
美国
起止时间：
1991-06-01 至 1994-05-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=9101385&HistoricalAwards=false
关键词：
Towards Overcoming Transitive Closure Bottleneck

项目摘要

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.

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