D. D. Sleator, R. E. Tarjan, A Data Structure for Dynamic Trees, Journal of Computer and System Sciences, Vol. 26, No. 3, 1983
A data structure is proposed to maintain a collection of vertex-disjoint trees under a
sequence of two kinds of operations: a link operation that combines two trees into one by
adding an edge, and a cut operation that divides one tree into two by deleting an edge. Each
operation requires O(log n) time. Using this data structure, new fast algorithms are obtained
for the following problems:(1) Computing nearest common ancestors.
(2) Solving various network flow problems including finding maximum flows, blocking flows, and acyclic flows.
(3) Computing certain kinds of constrained minimum spanning trees.
(4) Implementing the network simplex algorithm for minimum-cost flows.
The most significant application is (2); an O(mn log n)-time algorithm is obtained to find a
maximum flow in a network of n vertices and m edges, beating by a factor of log n the fastest
algorithm previously known for sparse graphs.