A linear algorithm for finding dominators in flow graphs and related problems

ABSTRACT

In the first part of the paper we show how to extend recent methods for solving a special case of the union-find problem in linear time, to a special case of the eval-link-update problem for computing the minimum function defined on paths of trees. In the cases where our approach is applicable, we give a way to perform m eval, link, and update operations on n elements in O(m + n) time and O(n) space, improved from O(m &agr;(m + n, n) + n) time and O(n) space in the more general case, where &agr; is a functional inverse of Ackermans function. The technique gives similar improvements in the efficiency of algorithms for solving several network optimization problems in the case where all the keys involved are integers in some suitable range. In the second part of the paper we show how to use the new technique for speeding up the fastest known algorithm for finding dominators in flow graphs so that it runs in linear time. We introduce the notions of pseudo and external dominators which are both computable in linear time and make the technique introduced in the first part applicable for finding immediate dominators. We first give an algorithm for a limited class of graphs which include cycle free graphs, and thus can be used to find dominators in reducible flow graphs. We then show how to extend our technique for computing dominators on any flow graph. All the algorithms we describe run on a Random Access Machine.

REFERENCES

• AHU74: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• AU72: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• AU77: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• CH78: Chin, F.Y., and Houck, D.J., 'Algorithms for Updating Minimal Cost Spanning Trees,' Jourhal of Computer and S~lstems Science, vol. 16 pp. 333-344, 1978.
• FT84: Fredman, M.L., and Tarjan, R.E., ~Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms," Proceedings of the 15th Annual FOCS, Oct. 1984.
• F83: Greg N. Frederickson, Data structures for on-line updating of minimum spanning trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.252-257, December 1983 [doi>10.1145/800061.808754]
• G77: Gabow, H.N., "Two Algorithms for Generating Weighted Spanning Trees In Order," SIAM Journal of Computing, vol. 6 no. 1, pp. 139-150, March 1977.
• GT83: Harold N. Gabow , Robert Endre Tarjan, A linear-time algorithm for a special case of disjoint set union, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.246-251, December 1983 [doi>10.1145/800061.808753]
• H80: Harel, D., 'A Linear Time Algorithm for the Lowest Common Ancesbars Problem", Proceedings 21 {EEE Syrup. on Foundations of Computer Science, pp. 308-319, 1980.
• H83: Harel, D., "On Line Maintenance of the Connected Components of' Dynamic Graphs," SIAM Journal of Computb~g, To Appear.
• HT83: Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
• H77: Matthew S. Hecht, Flow Analysis of Computer Programs, Elsevier Science Inc., New York, NY, 1977
• H69: Hu, T.C., Integer Programming and Network Flows, Addison Wesley, Reading, Massachusetts 1969, pp. 129-150.
• LM69: 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]
• LT79: Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979 [doi>10.1145/357062.357071]
• PM72: 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]
• T72: Tarjan, R.E., "Depth First Search and Linear Graph Algorithms," SIAM Journal o)r Computing, vol. 1, pp. 146-160, {972.
• T74: Tarjan, R.E., "Finding Dominators in Directed Graphs," SIAM Journal on Computing, vol. 3, pp. 62-89, 1974.
• T75: 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]
• T79: 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]
• T83: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983

INDEX TERMS

Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees; Graphs and networks

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

General Terms:
Algorithms, Theory, Verification