3
$\begingroup$

I am trying to write a data structure that given a general tree (or forest) will support the following operations:

  1. Edge deletion
  2. Connected(u,v) queries

This problem is addressed in section two of the following ACM journal article: "An On-Line Edge-Deletion Problem". The idea given claims to be able to carry out q edge deletions in O(q + |V|log|V|) time, while allowing constant time Connected(u,v) queries. The idea being: to maintain a table mapping each vertex to a connected component. Upon each deletion, each of the new trees is scanned in parallel. Which ever tree is finished being scanned first - becomes a new component. Now my question is, which graph representation can I use to implement their idea? On one hand I need to be able to delete an edge without having to scan an O(|V|) adjacency list, on the other hand, I need to be able to run a traversal (DFS) in O(|E|) = O(|V| (tree) time which can't happen using a matrix.

$\endgroup$
  • $\begingroup$ I just realized that I can run the parallel traversals before deleting the edge, and delete it during the traversal once its discovered. I guess that answers the question. $\endgroup$ – Yechiel Labunskiy Oct 30 '14 at 19:14
  • $\begingroup$ In addition to the adjacency list, each node points to its parent (or null, if no parent exists). To check whether $u$ and $v$ are adjacent check whether $u = parent(v) \vee v = parent(u)$. $\endgroup$ – daniello Oct 30 '14 at 21:34
3
$\begingroup$

This problem is known as Decremental Connectivity. In general, decremental connectivity is where you need to support the operations:

  • Connected($u$,$v$) : Check whether vertex $u$ is connected to vertex $v$
  • Delete($e$): Remove an edge $e$

Given $n$ queries of the first kind and $m$ queries of the second, Even and Shiloach [1] gave an $O(n\log{n} + m)$ algorithm and later, Alstrup et al. gave an $O(n+m)$ algorithm in [2].

There is a simple way to do the former using a data-structure known as the Euler Tour Trees or the approach taken in [1] could also be used. If you wish to implement [1], the tree is stored as a set of connected components. It is then enough to determine which component each vertex belongs to answer the connected-ness query. There is a breadth-first seach used to answer the deletion process. But it is $O(\log{n})$ amortized. This would achieve $O(n\log{n} + m)$.

If the $\log{n}$ factor must be removed, then a leaf-trimming approach would work. You trim all subtrees with size $\geq\log{n}$. Then, you can use the Euler Tour Trees (or the approach in [1]) to perform queries in the untrimmed portion. Some cases could need to be seperately handled. This is the approach given in [2].

[1] S. Even and Y. Shiloah. An on-line edge-deletion problem. Journal of the Assoiation for Computing Mahinery, 28:1-4, 1981.

[2] Stephen Alstrup and Jens Peter Secher and Maz Spork. Optimal On-line Decremental Connectivity in Trees, IPL, 65:64-8, 1997

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