A data structure for dynamic trees

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 O(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 O(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.

REFERENCES

• 1: A. V. Aho, J. E. Hopcroft, and J. D. Ullman, "On Finding Lowest Common Ancestors in Trees," SIAM J. Comput. 5 (1975), 115-132.
• 2: S. W. Bent, D. D. Sleator, and R. E. Tarjan, "Biased 2-3 Trees," Proc. 21stAnnual Symp. on Foundations of Computer Science (1980), 248-254.
• 3: B. V. Cherkasky, "An Algorithm for Construction of Maximal Flows in Networks with Complexity 0(V2@@@@E) Operations," Matematicheskie Metody Resheniia Ekonomicheskikh Zadach (Mathematical Methods for the Solution of Economic Problems) 7, 117-125 (in Russian).
• 4: C. V. Chvatal, Linear Programming, W. H. Freeman, San Francisco, California, to appear.
• 5: E. A. Dinits, "Algorithm for Solution of a Problem of Maximal Flow in a Network with Power Estimation," Soviet Math. Dokl. 11 (1970), 1277-1280.
• 6: Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
• 7: L. R. Ford and D. R. Fulkerson, Flows in Networks, Princeton University Press, Princeton, N.J., 1962.
• 8: H. N. Gabow and R. E. Tarjan, "Efficient Algorithms for Simple Matroid Intersection Problems," Proc. 20thAnnual Symp. on Foundations of Computer Science (1979), 196-204.
• 9: Z. Galil, "A New Algorithm for the Maximal Flow Problem", Proc. 19thSymp. on Foundations of Computer Science (1978), 231-245.
• 10: Zvi Galil , Amnon Naamad, Network flow and generalized path compression, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.13-26, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804394]
• 11: D. Harel, "A Linear Time Algorithm for the Lowest Common Ancestors Problem," Proc. 21st Annual Symp. on Foundations of Computer Science (1980), 308-319.
• 12: J. E. Hopcroft and J. D. Ullman, "Set-Merging Algorithms," SIAM J. Comput. 2 (1973), 294-303.
• 13: A. V. Karzanov, "Determining the Maximal Flow in a Network by the Method of Preflows," Soviet Math. Dokl. 15 (1974), 434-437.
• 14: D. Maier, "An Efficient Method for Storing Ancestor Information in Trees," SIAM J. Comput. 8 (1979), 599-618.
• 15: Yossi Shiloach, An O($n\cdot I \log^2 I$) maximum-flow algorithm, Stanford University, Stanford, CA, 1978
• 16: Daniel Dominic Kaplan Sleator, An o(nm log n) algorithm for maximum network flow, 1981
• 17: Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
• 18: Robert Endre Tarjan, Applications of Path Compression on Balanced Trees, Journal of the ACM (JACM), v.26 n.4, p.690-715, Oct. 1979 [doi>10.1145/322154.322161]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

General Terms:
Theory