A Fast Algorithm for Finding Dominators in a Flowgraph

Thomas Lengauer, Robert Endre Tarjan

Research output: Contribution to journalArticle

377 Scopus citations

Abstract

A fast algorithm for finding dominators in a flowgraph is presented. The algorithm uses depth-first search and an efficient method of computing functions defined on paths in trees. A simple implementation of the algorithm runs in O(m log n) time, where m is the number of edges and n is the number of vertices in the problem graph. A more sophisticated implementation runs in O(mα(m, n)) time, where α(m, n) is a functional inverse of Ackermann's function.Both versions of the algorithm were implemented in Algol W, a Stanford University version of Algol, and tested on an IBM 370/168. The programs were compared with an implementation by Purdom and Moore of a straightforward O(mn)-time algorithm, and with a bit vector algorithm described by Aho and Ullman. The fast algorithm beat the straightforward algorithm and the bit vector algorithm on all but the smallest graphs tested.

Original languageEnglish (US)
Pages (from-to)121-141
Number of pages21
JournalACM Transactions on Programming Languages and Systems (TOPLAS)
Volume1
Issue number1
DOIs
StatePublished - Jan 1 1979
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • depth-first search
  • dominators
  • global flow analysis
  • graph algorithm
  • path compression

Fingerprint Dive into the research topics of 'A Fast Algorithm for Finding Dominators in a Flowgraph'. Together they form a unique fingerprint.

  • Cite this