TY - GEN

T1 - A data structure for dynamic trees

AU - Sleator, Daniel D.

AU - Tarjan, Robert Endre

N1 - Publisher Copyright:
© 1981 ACM.

PY - 1981/5/11

Y1 - 1981/5/11

N2 - We propose a data structure 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. Our data structure requires 0(log n) time per operation when the time is amortized over a sequence of operations. Using our data structure, we obtain new fast algorithms for the following problems: (1) Computing deepest 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 the transshipment problem. Our most significant application is (2); we obtain an 0(mn log n)-time algorithm 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.

AB - We propose a data structure 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. Our data structure requires 0(log n) time per operation when the time is amortized over a sequence of operations. Using our data structure, we obtain new fast algorithms for the following problems: (1) Computing deepest 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 the transshipment problem. Our most significant application is (2); we obtain an 0(mn log n)-time algorithm 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.

UR - http://www.scopus.com/inward/record.url?scp=84974568193&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84974568193&partnerID=8YFLogxK

U2 - 10.1145/800076.802464

DO - 10.1145/800076.802464

M3 - Conference contribution

AN - SCOPUS:84974568193

SN - 0897910419

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 114

EP - 122

BT - Conference Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC 1981

PB - Association for Computing Machinery

T2 - 13th Annual ACM Symposium on Theory of Computing, STOC 1981

Y2 - 11 June 1981 through 13 June 1981

ER -