A fast algorithm for finding dominators in a flowgraph
- 1 January 1979
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 1 (1), 121-141
- https://doi.org/10.1145/357062.357071
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.Keywords
This publication has 5 references indexed in Scilit:
- Applications of Path Compression on Balanced TreesJournal of the ACM, 1979
- Algorithm 430 [H]: Immediate predominators in a directed graphCommunications of the ACM, 1972
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972
- Object code optimizationCommunications of the ACM, 1969
- Zum Hilbertschen Aufbau der reellen ZahlenMathematische Annalen, 1928