Editing Transitive closure (section)

== Algorithms ==
Efficient algorithms for computing the transitive closure of the adjacency relation of a graph can be found in {{harvtxt|Nuutila|1995}}. Reducing the problem to multiplications of adjacency matrices achieves the  time complexity of [[matrix multiplication]],<ref>{{harvnb|Munro|1971}}, {{harvnb|Fischer|Meyer|1971}}</ref> <math>O(n^{2.3728596})</math>. However, this approach is not practical since both the constant factors and the memory consumption for sparse graphs are high {{harv|Nuutila|1995|pp=22–23|loc=sect.2.3.3}}. The problem can also be solved by the [[Floyd–Warshall algorithm]] in <math>O(n^3)</math>, or by repeated [[breadth-first search]] or [[depth-first search]] starting from each node of the graph.

For directed graphs, [[Purdom's algorithm]] solves the problem by first computing its condensation DAG and its transitive closure, then lifting it to the original graph. Its runtime is <math>O(m+\mu n)</math>, where <math>\mu</math> is the number of edges between its [[strongly connected component]]s.<ref name=Purdom>{{cite journal | doi=10.1007/BF01940892 | url= http://digital.library.wisc.edu/1793/57514| first=Paul |last=Purdom Jr. | title=A transitive closure algorithm | journal=[[BIT Numerical Mathematics]] | volume=10 | number=1 | pages=76&ndash;94 | date=Mar 1970 }}</ref><ref>{{cite report | url=https://minds.wisconsin.edu/handle/1793/57514 | author=Paul W. Purdom Jr. | title=A transitive closure algorithm | institution=[[University of Wisconsin-Madison]] | type=Computer Sciences Technical Report | volume=33 | date=Jul 1968 }}</ref><ref>{{cite web
| url=https://algowiki-project.org/algowiki/en/index.php?title=Purdom%27s_algorithm&oldid=10286
| title="Purdom's algorithm" on AlgoWiki}}</ref><ref>{{cite web
| url=https://algowiki-project.org/algowiki/en/index.php?title=Transitive_closure_of_a_directed_graph&oldid=1475
| title="Transitive closure of a directed graph" on AlgoWiki}}</ref>

More recent research has explored efficient ways of computing transitive closure on distributed systems based on the [[MapReduce]] paradigm.<ref>(Afrati et al. 2011)</ref>