4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Do you want constant query time? $\endgroup$ – George Apr 12 '13 at 13:39
  • $\begingroup$ Yes, constant query time. I have updated the question. $\endgroup$ – wei wang Apr 13 '13 at 11:39
  • 1
    $\begingroup$ Directed or undirected trees? $\endgroup$ – David Eppstein Apr 13 '13 at 15:10
  • 1
    $\begingroup$ 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? $\endgroup$ – David Eppstein Apr 14 '13 at 0:09
  • $\begingroup$ It should be "a forest on a fixed vertex set" and directed trees. $\endgroup$ – wei wang Apr 14 '13 at 8:42
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.