<p>The best I can find for this is $O(\log n)$ amortized update time with constant query time. The basic idea is that if you know both preorder and postorder for a tree, you can recover reachability: there is a path from $x$ to $y$ iff $x$ is before $y$ in preorder and after it in postorder.</p>

<p>There are several data structures that can maintain a list of items, allowing insertions immediately before or after one particular item, deletions, and constant time ordering queries, in constant time per operation; see e.g. <a href="http://erikdemaine.org/papers/DietzSleator_ESA2002/paper.pdf" rel="nofollow">http://erikdemaine.org/papers/DietzSleator_ESA2002/paper.pdf</a>. Record for each node which tree it belongs to, and use one of these structures for the preorder and postorder of each tree. If these structures do not already do this for you, also use a linked list so you can read off the tree nodes in either order.</p>

<p>To add an edge from a node $x$ to a node $y$ (where prior to the addition, $y$ is the root of a tree) we need to merge the orderings for two trees. Do so by finding which of the two trees is smaller, adding its vertices into the ordering structures for the tree that is larger, and changing the node labels on the nodes in the smaller tree to point to the larger one. In this way, each vertex participates in $O(\log n)$ updates over the lifetime of the structure (every time it is part of the smaller tree, the size of the tree it is in doubles). More precisely, each tree with $k$ edges takes total time $O(k\log k)$ to build, so the amortized time per edge is logarithmic.</p>

CC BY-SA 3.0
2013-04-14T15:13:23.480Z
2013-04-14T18:15:27.127Z
2013-04-14T18:15:27.127Z
David Eppstein
<p>As the title. The dynamic algorithm maintains the transitive closure of a tree when the tree undergoes a series of edge insertions (but no deletions)? And the algorithm supports constant query time.</p>

<p>The paper (G.F. Italiano. Amortized efficiency of a path retrieval data structure. Theoretical Computer Science, 48(2–3):273–281, 1986.) introduces an algorithm for maintaining the transitive closure of a graph with O(n) amortized time pre  insertion. I wonder whether better algorithm exists for trees?</p>

CC BY-SA 3.0
2013-04-12T13:39:21.157Z
Do you want constant query time?
George
CC BY-SA 3.0
2013-04-13T11:39:09.783Z
Yes, constant query time. I have updated the question.
wei wang
CC BY-SA 3.0
2013-04-13T15:10:46.097Z
Directed or undirected trees?
David Eppstein
CC BY-SA 3.0
2013-04-14T00:09:05.803Z
Also, what do you mean by a tree undergoing edge insertions? Unless the vertex set changes, the number of edges in a tree cannot change. Do you mean that you have a forest on a fixed vertex set? Or do you mean that you have a tree, and can insert a new leaf vertex?
David Eppstein
CC BY-SA 3.0
2013-04-14T08:42:51.730Z
It should be "a forest on a fixed vertex set" and directed trees.
wei wang
<ds.algorithms><graph-theory><ds.data-structures><dynamic-algorithms>
What is the fastest deterministic algorithm for incremental dynamic tree reachability?
wei wang
# What is the fastest deterministic algorithm for incremental dynamic tree reachability?

(Asked by: username_0 on 2013-04-12)

As the title. The dynamic algorithm maintains the transitive closure of a tree when the tree undergoes a series of edge insertions (but no deletions)? And the algorithm supports constant query time.

The paper (G.F. Italiano. Amortized efficiency of a path retrieval data structure. Theoretical Computer Science, 48(2–3):273–281, 1986.) introduces an algorithm for maintaining the transitive closure of a graph with O(n) amortized time pre insertion. I wonder whether better algorithm exists for trees?

**Tags:** ds.algorithms, graph-theory, ds.data-structures, dynamic-algorithms
> **Comments:**
> **username_1**: Do you want constant query time?  
> **username_0**: Yes, constant query time. I have updated the question.  
> **username_2**: Directed or undirected trees?  
> **username_2**: Also, what do you mean by a tree undergoing edge insertions? Unless the vertex set changes, the number of edges in a tree cannot change. Do you mean that you have a forest on a fixed vertex set? Or do you mean that you have a tree, and can insert a new leaf vertex?  
> **username_0**: It should be "a forest on a fixed vertex set" and directed trees.  

---

## 1 answers

### Answer by username_2 on 2013-04-14. Score: 4

The best I can find for this is $O(\log n)$ amortized update time with constant query time. The basic idea is that if you know both preorder and postorder for a tree, you can recover reachability: there is a path from $x$ to $y$ iff $x$ is before $y$ in preorder and after it in postorder.

There are several data structures that can maintain a list of items, allowing insertions immediately before or after one particular item, deletions, and constant time ordering queries, in constant time per operation; see e.g. <http://erikdemaine.org/papers/DietzSleator_ESA2002/paper.pdf>. Record for each node which tree it belongs to, and use one of these structures for the preorder and postorder of each tree. If these structures do not already do this for you, also use a linked list so you can read off the tree nodes in either order.

To add an edge from a node $x$ to a node $y$ (where prior to the addition, $y$ is the root of a tree) we need to merge the orderings for two trees. Do so by finding which of the two trees is smaller, adding its vertices into the ordering structures for the tree that is larger, and changing the node labels on the nodes in the smaller tree to point to the larger one. In this way, each vertex participates in $O(\log n)$ updates over the lifetime of the structure (every time it is part of the smaller tree, the size of the tree it is in doubles). More precisely, each tree with $k$ edges takes total time $O(k\log k)$ to build, so the amortized time per edge is logarithmic.


---

