On finding lowest common ancestors in trees

ABSTRACT

Trees in an n node forest are to be merged according to instructions in a given sequence, while other instructions in the sequence ask for the lowest common ancestor of pairs of nodes. We show that any sequence of O(n) instructions can be processed “on line” in O(n log n) steps on a random access computer. If we can accept our answer “off-line”, that is, no answers need to be produced until the entire sequence of instructions has been seen seen, then we may perform the task in O(n G(n)) steps, where G(n) is the number of times we must apply log2 to n to obtain a number less than or equal to zero. A third algorithm solves a problem of intermediate complexity. We require the answers on line, but we suppose that all tree merging instructions precede the information requests. This algorithm requires O(n log log n) time. We apply the first on line algorithm to a problem in code optimization, that of computing immediate dominators in a reducible flow graph. We show how this computation can be performed in O(n log n) steps.

REFERENCES

• 1: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 2: J. E. Hopcroft and J. D. Ullman, "Set Merging Algorithms," Submitted to SIAM J. Computing.
• 3: Edward S. Lowry , C. W. Medlock, Object code optimization, Communications of the ACM, v.12 n.1, p.13-22, Jan. 1969 [doi>10.1145/362835.362838]
• 4: Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 5: Marvin Schaefer, A mathematical theory of global program optimization (Prentice-Hall series in automatic computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1973
• 6: Paul W. Purdom, Jr. , Edward F. Moore, Immediate predominators in a directed graph [H], Communications of the ACM, v.15 n.8, p.777-778, Aug. 1972 [doi>10.1145/361532.361566]
• 7: Frances E. Allen, Control flow analysis, ACM SIGPLAN Notices, v.5 n.7, p.1-19, July 1970
• 8: J. Cocke and R. E. Miller, "Some Analysis Techniques for Optimizing Computer Programs," Proc. Second International Conference on System Sciences, Honolulu, Hawaii, 1969.
• 9: John Cocke, Global common subexpression elimination, ACM SIGPLAN Notices, v.5 n.7, p.20-24, July 1970
• 10: J. D. Ullman, "Fast Algorithms for the Elimination of Common Subexpressions," Technical Report TR-106, Department of Electrical Engineering, Computer Sciences Laboratory, March, 1972. Also in Proc. IEEE 13th Annual Symposium on Switching and Automata Theory, October, 1972.
• 11: K. Kennedy, "A Global Flow Analysis Algorithm," International J. Computer Mathematics, 3:1 (December 1971), 5-16.
• 12: M. S. Hecht and J. D. Ullman, "Flow Graph Reducibility," SIAM. J. Computing, 1:2 (June 1972), 188-202.
• 13: R. E. Tarjan, "Testing Flow Graph Reducibility," Department of Computer Science, Cornell University, Ithaca, N.Y.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

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

General Terms:
Algorithms, Theory