Handbook of Data Structures and Applications, 2nd Edition

36

Dynamic Trees^*

Camil Demetrescu

Sapienza University of Rome

Irene Finocchi

Sapienza University of Rome

Giuseppe F. Italiano

University of Rome Tor Vergata

36.1Introduction

36.2Linking and Cutting Trees

Using Operations on Vertex-Disjoint Paths•Implementing Operations on Vertex-Disjoint Paths

36.3Topology Trees

Construction•Updates•Applications

36.4Top Trees

Updates•Representation and Applications

36.5ET Trees

Updates•Applications

36.6Reachability Trees

36.7Conclusions

Acknowledgments

References

36.1Introduction

In this chapter we consider the problem of maintaining properties of a collection of vertex-disjoint trees that change over time as edges are added or deleted. The trees can be rooted or free, and vertices and edges may be associated ...