Finding Dominators Revisited

Loukas Georgiadis, Robert Endre Tarjan

Research output: Contribution to conferencePaper

40 Scopus citations

Abstract

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)
Pages862-871
Number of pages10
StatePublished - Apr 15 2004
EventProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States
Duration: Jan 11 2004Jan 13 2004

Other

OtherProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityNew Orleans, LA.
Period1/11/041/13/04

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

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

  • Cite this

    Georgiadis, L., & Tarjan, R. E. (2004). Finding Dominators Revisited. 862-871. Paper presented at Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA., United States.