Article ID: | iaor1999861 |
Country: | Netherlands |
Volume: | 78 |
Issue: | 2 |
Start Page Number: | 169 |
End Page Number: | 177 |
Publication Date: | Aug 1997 |
Journal: | Mathematical Programming |
Authors: | Tarjan Robert E. |
Keywords: | networks, computers: data-structure |
The dynamic tree> is an abstract data type that allows the maintenance of a collection of trees subject to joining by adding edges (linking) and splitting by deleting edges (cutting), while at the same time allowing reporting of certain combinations of vertex or edge values. For many applications of dynamic trees, values must be combined along paths. For other applications, values must be combined over entire trees. For the latter situation, an idea used originally in parallel graph algorithms, to represent trees by Euler tours, leads to a simple implementation with a time of O(log