有向图最著名的传递闭包算法是什么? [英] What is the best known transitive closure algorithm for a directed graph?

问题描述

就运行时间而言，最著名的有向图传递闭包算法是什么?

In terms of runtime, what is the best known transitive closure algorithm for directed graphs?

我目前正在使用 Warshall 的算法，但它的 O(n^3).虽然，由于图形表示，我的实现稍微好一点(而不是检查所有边，它只检查所有去边).有没有比这更好的传递闭包算法?特别是，有没有什么专门针对共享内存多线程架构的?

I am currently using Warshall's algorithm but its O(n^3). Although, due to the graph representation my implementation does slightly better (instead of checking all edges, it only checks all out going edges). Is there any transitive closure algorithm which is better than this? In particular, is there anything specifically for shared memory multi-threaded architectures?

推荐答案

本文讨论了各种传递闭包算法的性能:

This paper discusses the performance of various transitive closure algorithms:

http://www.vldb.org/conf/1988/P382.PDF

论文中一个有趣的想法是避免随着图的变化重新计算整个闭包.

One interesting idea from the paper is to avoid recomputing the entire closure as the graph changes.

还有 Esko Nuutila 的这个页面，其中列出了一些最近的算法:

There is also this page by Esko Nuutila, which lists a couple of more recent algorithms:

http://www.cs.hut.fi/~enu/tc.html

该页面上列出的他的博士论文可能是最好的起点:

His PhD thesis listed on that page may be the best place to start:

http://www.cs.hut.fi/~enu/thesis.html

从那个页面:

实验还表明，用区间表示和新算法，可以计算传递闭包通常在时间上与输入图的大小成线性关系.

The experiments also indicate that with the interval representation and the new algorithms, the transitive closure can be computed typically in time linear to the size of the input graph.

这篇关于有向图最著名的传递闭包算法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！