<p>O(n) time per edge addition:</p>

<ul>
<li><p>G. F. Italiano (1986): <a href="http://dx.doi.org/10.1016/0304-3975%2886%2990098-8">Amortized efficiency of a path retrieval data structure</a>, <em>Theoretical Computer Science</em> 48, 273–281.</p></li>
<li><p>J. A. La Poutré and J. van Leeuwen (1988): <a href="http://dx.doi.org/10.1007/3-540-19422-3_9">Maintenance of transitive closures and transitive reductions of graphs</a>, <em>Proc. WG 1987</em>.</p></li>
</ul>

CC BY-SA 4.0
2020-03-08T20:49:28.353Z
@Alexandru The first paper provides a nxn table which lets you determine if one node is reachable from another in constant time. So to iterate over all nodes reachable from a given node, just iterate that column and see which pointers are non-null. Or you could just iterate the descendant tree, which is O(k) where k is the number of reachable nodes.
Antimony
CC BY-SA 4.0
2021-10-06T14:37:24.767Z
Italiano algorithm is really good. Super fast, easy to understand and implement.
Mu-Tsun Tsai
CC BY-SA 2.5
2010-09-03T15:34:15.840Z
First paper provides two important operations from transitive closure, but I need a third one: iterating through all accessible nodes. The second paper is good, though.
Alexandru
CC BY-SA 2.5
2010-08-16T21:23:54.150Z
See also: D. M. Yellin. Speeding up dynamic transitive closure for bounded degree graphs. Acta Informatica, 30:369–384, 1993.
Jeffε
CC BY-SA 2.5
2010-08-16T21:16:50.027Z
2010-08-16T21:24:08.673Z
2010-08-16T21:24:08.673Z
Jukka Suomela
<p>I'm looking for an online algorithm to maintain the transitive closure of a directed acyclic graph with a time complexity less than O(N^2) per edge addition. My current algorithm is like this: </p>

<pre><code>For every new edge u-&gt;v connect all nodes in Pred(u) \cup { u } with all nodes in Succ(v) \ \cup { v }.
</code></pre>

<p>For O(N^2) edges this translates in a total time complexity of O(N^4) which much worse than, for example, <a href="http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm">Floyd-Warshall</a>.</p>

<ds.algorithms><graph-theory><ds.data-structures><transitive-closure>
Online transitive closure better than O(N^2) per edge addition
Alexandru
# Online transitive closure better than O(N^2) per edge addition

(Asked by: username_0 on 2010-08-16)

I'm looking for an online algorithm to maintain the transitive closure of a directed acyclic graph with a time complexity less than O(N^2) per edge addition. My current algorithm is like this: 
For every new edge u->v connect all nodes in Pred(u) \cup { u } with all nodes in Succ(v) \ \cup { v }.

For O(N^2) edges this translates in a total time complexity of O(N^4) which much worse than, for example, Floyd-Warshall.

**Tags:** ds.algorithms, graph-theory, ds.data-structures, transitive-closure

---

## 1 answers

### Answer by username_1 on 2010-08-16. Score: 17 | Accepted answer

O(n) time per edge addition:

* G. F. Italiano (1986): [Amortized efficiency of a path retrieval data structure](http://dx.doi.org/10.1016/0304-3975%2886%2990098-8), *Theoretical Computer Science* 48, 273–281.
* J. A. La Poutré and J. van Leeuwen (1988): [Maintenance of transitive closures and transitive reductions of graphs](http://dx.doi.org/10.1007/3-540-19422-3_9), *Proc. WG 1987*.

> **Comments:**
> **username_4**: See also: D. M. Yellin. Speeding up dynamic transitive closure for bounded degree graphs. Acta Informatica, 30:369–384, 1993.  
> **username_0**: First paper provides two important operations from transitive closure, but I need a third one: iterating through all accessible nodes. The second paper is good, though.  
> **username_2**: @Alexandru The first paper provides a nxn table which lets you determine if one node is reachable from another in constant time. So to iterate over all nodes reachable from a given node, just iterate that column and see which pointers are non-null. Or you could just iterate the descendant tree, which is O(k) where k is the number of reachable nodes.  
> **username_3**: Italiano algorithm is really good. Super fast, easy to understand and implement.  

---

