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: alinkoperation that combines two trees into one by

adding an edge, and acutoperation that divides one tree into two by deleting an edge. Each

operation requiresO(logn) 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); anO(mnlogn)-time algorithm is obtained to find a

maximum flow in a network ofnvertices andmedges, beating by a factor of lognthe fastest

algorithm previously known for sparse graphs.

Daniel Sleator: Email, Home Page, Papers

Last modified: Sat Jan 21 07:15:44 EST 2006