Corrigendum: a new, simpler linear-time dominators algorithm

ABSTRACT

Corrigendum to ACM Transactions on Programming Languages and Systems, 20(6):1265--1296, 1998.

REFERENCES

• 1: Stephen Alstrup , Dov Harel , Peter W. Lauridsen , Mikkel Thorup, Dominators in Linear Time, SIAM Journal on Computing, v.28 n.6, p.2117-2132, Dec. 1999 [doi>10.1137/S0097539797317263]
• 2: Adam L. Buchsbaum , Haim Kaplan , Anne Rogers , Jeffery R. Westbrook, A new, simpler linear-time dominators algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.6, p.1265-1296, Nov. 1998 [doi>10.1145/295656.295663]
• 3: Gabow, H. N. and Tarjan, R. E. 1985. A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30, 2, 209--221.
• 4: Loukas Georgiadis , Robert E. Tarjan, Finding dominators revisited: extended abstract, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 5: 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]
• 6: 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:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

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

General Terms:
Algorithms, Languages, Performance, Theory

Keywords:
Compilers, dominators, flowgraphs, microtrees, path compression