20. Dynamic Graphs II

MIT 6.851 Advanced Data Structures, Spring 2012
Instructor: Erik Demaine

Dynamic graphs: Euler tour trees, decremental connectivity in trees in O(1), fully dynamic connectivity in O(lg2 n), survey

License: Creative Commons BY-NC-SA

[davidharmeyer]

Excellent lecture! A couple questions:


I agree that it is possible to reroot an Euler Tour Tree defined as you wrote it in log(n) time if, say, you implement the ETT with a treap. But how on earth do you maintain the pointers to the first and last instance of each node in the tree if you do that?


Second, why do we need to be efficient in our DFS like you talk about at 1:19:53? if we just do it naively, we will hit nodes that have no edges of the right level, but all of those nodes will also be incident to a tree edge that we have to push down anyway, so I don't see the issue with a naive DFS...

[Dacinthewizard]

So i've attempted to implement euler tour trees based on the explaination in this video, but i struggle to maintain the pointers to the first & last occurrence of a vertex when performing a link operation where v isn't the root of it's represented tree, as you then have to make v the root of it's represented tree which i did by removing the last node of v's auxTree, splitting the auxTree after the last occurrence of v and the concatenating the 2 tree in reverse order. (if you cut a BBST and the concatenate the 2 halves in reverse order, you loose the information of first/last in more than polylog(N) nodes(for example in one long path when you make the bottom most node of the represented Tree the root)).

Maintaining the subtree-augmentation of whether there are any nodes with edges of the current level seems even more difficult (as i could fix the problem with first/last using a binary search on the occurences of a vertex to find it's first/last occurence in the auxTree and just get an extra log(N) factor

[sudipandatta]

can anyone share an implementation or problem on decremental dynamic connectivity