A data structure for dynamic trees

Daniel D. Sleator, Robert Endre Tarjan

Research output: Contribution to journalArticlepeer-review

758 Scopus citations

Abstract

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. (1) Computing nearest common ancestors. 2. (2) Solving various network flow problems including finding maximum flows, blocking flows, and acyclic flows. 3. (3) Computing certain kinds of constrained minimum spanning trees. 4. (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.

Original languageEnglish (US)
Pages (from-to)362-391
Number of pages30
JournalJournal of Computer and System Sciences
Volume26
Issue number3
DOIs
StatePublished - Jun 1983
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

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

Cite this