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

问题描述

在运行时方面，有向图最著名的传递闭包算法是什么？

我目前正在使用Warshall算法，但其O（n ^ 3）。尽管由于图形表示，我的实现稍好一些（而不是检查所有边缘，而是仅检查所有向外的边缘）。有没有比这更好的传递闭包算法？

解决方案

本文特别讨论了各种传递闭包算法的性能。 ：

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

本文中的一个有趣的想法是，避免在图形变化时重新计算整个闭合。 / p>

Esko Nuutila也有此页面，其中列出了一些最新算法：

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

该页面上列出的博士学位论文可能是最好的起点：

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

从该页面：

实验还表明t在使用间隔表示
和新算法的情况下，可以通常在与输入图的大小呈线性关系的时间内计算
的传递闭包。

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

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.

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

From that page:

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屋！