Finding Dominators Revisited

Loukas Georgiadis, Robert E. Tarjan

Research output: Contribution to conferencePaperpeer-review

44 Scopus citations


The problem of finding dominators in a flowgraph arises in many kinds of global code optimization and other settings. In 1979 Lengauer and Tarjan gave an almost-linear-time algorithm to find dominators. In 1985 Harel claimed a linear-time algorithm, but this algorithm was incomplete; Alstrup et al. [1999] gave a complete and "simpler" linear-time algorithm on a random-access machine. In 1998, Buchsbaum et al. claimed a "new, simpler" linear-time algorithm with implementations both on a random access machine and on a pointer machine. In this paper, we begin by noting that the key lemma of Buchsbaum et al. does not in fact apply to their algorithm, and their algorithm does not run in linear time. Then we provide a complete, correct, simpler linear-time dominators algorithm. One key result is a linear-time reduction of the dominators problem to a nearest common ancestors problem, implementable on either a random-access machine or a pointer machine.

Original languageEnglish (US)
Number of pages10
StatePublished - 2004
EventProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States
Duration: Jan 11 2004Jan 13 2004


OtherProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityNew Orleans, LA.

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics


Dive into the research topics of 'Finding Dominators Revisited'. Together they form a unique fingerprint.

Cite this