A data structure for dynamic trees

Daniel D. Sleator, Robert Endre Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

50 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationConference Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC 1981
PublisherAssociation for Computing Machinery
Pages114-122
Number of pages9
ISBN (Print)0897910419
DOIs
StatePublished - May 11 1981
Externally publishedYes
Event13th Annual ACM Symposium on Theory of Computing, STOC 1981 - Milwaukee, United States
Duration: Jun 11 1981Jun 13 1981

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other13th Annual ACM Symposium on Theory of Computing, STOC 1981
CountryUnited States
CityMilwaukee
Period6/11/816/13/81

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'A data structure for dynamic trees'. Together they form a unique fingerprint.

Cite this