### 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 language | English (US) |
---|---|

Pages (from-to) | 121-141 |

Number of pages | 21 |

Journal | ACM Transactions on Programming Languages and Systems (TOPLAS) |

Volume | 1 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1 1979 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

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