5. Linking and Cutting Trees
Robert Endre Tarjan · Society for Industrial and Applied Mathematics eBooks · 1983
5.1. The problem of linking and cutting trees. The trees we have studied in Chapters 2, 3 and 4 generally occur indirectly in network algorithms, as concrete representations of abstract data structures. Trees also occur more directly in such algorithms, either as part of the problem statement or because they express the behavior of the algorithm. In this chapter we shall study a generic tree manipulation problem that occurs in many network algorithms, including a maximum flow algorithm that we shall study in Chapter 8.