In their paper "Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity", Holm, de Lichtenberg, and Thorup describe a data structure for maintaining dynamic connectivity in undirected graphs. Their data structure maintains a collection of forests $F_0, F_1, F_2, ..., F_{\log_2 n}$ made of forests of edges of different levels. In the paper, the authors say that the forests should be represented by having an Euler tour tree data structure for each level. Each tree is augmented with information about the number of edges in the tree, the number of edges of each level in the tree, which subtrees contain nodes adjacent to edges of the given level, and which subtrees contain edges of the given level.

It seems like it should be possible to maintain all this information in a single Euler tour tree by augmenting each node in the tree with $\log_2 n$ copies of the above information, one for each level. This would simplify the presentation of the data structure without requiring redundant copies of each edge.

Does this modification work correctly? Or is there a reason to maintain a separate copy of the forests at each level?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.