Неліктен динамикалық графикалық деректер құрылымында ормандардың жинағын сақтау қажет?

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.

Бұл мәліметтерді ағаштың әрбір түйінін жоғарыда келтірілген мәліметтердің $ \ log_2 n $ көшірмелерін бір деңгейде ұлғайту арқылы бірегей Euler туристік ағашында сақтауға болады. Бұл әрбір құрылымның артық көшірмелерін талап етпестен деректер құрылымын ұсынуды оңайлатады.

Бұл өзгеріс дұрыс жұмыс істей ме? Немесе әр деңгейде ормандардың жеке көшірмесін сақтауға себеп бар ма?

Рахмет!

5

Жауап жоқ

0