1
$\begingroup$

I'm interested in the dynamic connectivity problem for forests. In this problem a forest is subject to updates (edge insertion that do not create cycles and edge deletion) and queries if two nodes are connected.

Link cut trees and Euler tour trees supports these three operations in $O(\log n)$ (Erik Demaine's notes). The results of Eppstein at. all (Sparsification—a technique for speeding up dynamic graph algorithms, JACM, 1997) for general graphs are $O(\sqrt n)$ for updates and $O(1)$ for queries.

In my use case queries are more common than updates, so I'm looking for an alternative structure (the Eppstein structure is too general and too complicated to implement) that supports updates in sublinear time and queries in constant time. Is there such structure?

$\endgroup$
  • $\begingroup$ Perhaps do union-find (so each node has a pointer to an ancestor up the tree); when you delete an edge, recursively traverse all nodes below the edge whose pointer points above the deleted edge. The running time of insert and query will be fast; delete will be slow. I don't know if one can prove an amortized sublinear time bound for delete in this kind of data structure. $\endgroup$ – D.W. Sep 28 '17 at 22:18
  • $\begingroup$ I found an answer to my own question that i would like to post here, but the section for answering is not showing up... Do you known why @D.W.? $\endgroup$ – malbarbo Oct 20 '17 at 12:35
  • $\begingroup$ Odd! I have no idea. Perhaps try from a different browser, and if that still doesn't resolve it, try contacting Stack Exchange via the 'contact' link below? $\endgroup$ – D.W. Oct 20 '17 at 13:40
  • $\begingroup$ @D.W. I was able so solve the issue. Thanks. $\endgroup$ – malbarbo Oct 20 '17 at 16:26
0
$\begingroup$

An Euler tour tree is a linear representation of a tree. When the tour is stored in a balanced binary search tree keyed (implicitly) by the index in tour, the update and query operations can be done in $O(\log n)$. This is described in the referenced Erik's notes.

The tour can be stored in a two level array (similar to the structure described in section 2.2 of Data Structures for Traveling Salesmen). Each tree tour is stored in $O(\sqrt n)$ arrays with $O(\sqrt n)$ elements in each. Each tour element keeps a reference to its array, and each array keeps an reference to its parent array.

The update operations involves a constant number of arrays so it can be done in $O(\sqrt n)$. The query operation can be done in $O(1)$: The root of the tree containing each element is found and then compared. Each root is found in the position 0 of the first array of the tree tour. To find the tree tour containing a element just follows the element reference to its array and then follows the link to the parent array (that is, the tree tour).

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