1
$\begingroup$

ST (or link cut) trees are a special kind of trees used for dynamic graph algorithms. They support the following operations in logarithmic time:

  • CUT(v) Deletes the edge from v to its parent
  • JOIN(v, w) Where v is a root vertex, assigns parent(v) ← w (makes v a child of w)
  • FIND_ROOT(v) Returns the root of the tree containing v

My question here is how to delete an arbitrary edge (u, v) from the tree, and what would be its complexity? If it is too complex or unfeasible to do that, can you point me to an algorithm ((pseudo)code) for the fully dynamic unweighted undirected graph connectivity problem. If it is of any help, the degree of every edge is guaranteed to be at most 2 at any point of the algorithm.

I've read quite a few papers on the topic but in almost all of them the authors only give us very high level descriptions of these structures, in the form of theorems.

$\endgroup$
2
$\begingroup$

For any edge $(u,v)$ either $u$ is $v$'s parent or vice versa. So you just call CUT for "deeper" vertex.

UPD: To determine which vertex is deeper you can use Access($v$). If after this operation $u$ is a rightmost node of $v$'s left (path)subtree, then $u$ is $v$'s parent and you can call CUT($v$) (or just $\mbox{left}(v) \gets \mbox{Null}$ because Access($v$) was called before). Else you call CUT($u$).

$\endgroup$
  • $\begingroup$ Thank you, great answer :D I wonder now if the complexity is still O(log(n)) if all the trees in the forests are in fact linear (lists), as I stated in the description? $\endgroup$ – dancsi Jan 9 '12 at 19:39
  • $\begingroup$ I've added more details to the answer. Yes, everything is $O(\log n)$ because you call Access and CUT not more than once and check if $u$ lies in $v$'s left subtree which is $O(\log n)$ too. $\endgroup$ – Dmytro Korduban Jan 9 '12 at 19:48

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.