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

<p>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$).</p>

CC BY-SA 3.0
2012-01-09T19:39:45.567Z
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?
dancsi
CC BY-SA 3.0
2012-01-09T19:48:52.397Z
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.
Dmytro Korduban
CC BY-SA 3.0
2012-01-09T19:29:00.403Z
2012-01-10T12:32:21.483Z
2012-01-10T12:32:21.483Z
Dmytro Korduban
<p><a href="http://www.cs.cmu.edu/afs/cs.cmu.edu/user/sleator/www/papers/dynamic-trees.pdf" rel="nofollow">ST</a> <a href="http://www.cs.uiuc.edu/~jeffe/teaching/datastructures/2006/notes/07-linkcut.pdf" rel="nofollow">(or link cut)</a> trees are a special kind of trees used for dynamic graph algorithms. They support the following operations in logarithmic time:</p>

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

<p>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, <strong>the degree of every edge is guaranteed to be at most 2</strong> at any point of the algorithm. </p>

<p>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.</p>

<graph-algorithms><ds.data-structures><tree><dynamic-algorithms>
Remove specific edge from ST (link-cut) tree
dancsi
# Remove specific edge from ST (link-cut) tree

(Asked by: username_0 on 2012-01-09)

[ST](http://www.cs.cmu.edu/afs/cs.cmu.edu/user/sleator/www/papers/dynamic-trees.pdf) [(or link cut)](http://www.cs.uiuc.edu/~jeffe/teaching/datastructures/2006/notes/07-linkcut.pdf) 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.

**Tags:** graph-algorithms, ds.data-structures, tree, dynamic-algorithms

---

## 1 answers

### Answer by username_1 on 2012-01-09. Score: 2 | Accepted answer

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$).

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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.  

---

