A fast algorithm for finding dominators in a flowgraph
Thomas Lengauer, Robert Endre Tarjan · ACM Transactions on Programming Languages and Systems · 1979
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.
Cited by 645 works. doi:10.1145/357062.357071
Authors
References
- The Art of Computer Programming
- Depth-First Search and Linear Graph Algorithms
- Principles of Compiler Design
- Zum Hilbertschen Aufbau der reellen Zahlen
- Object code optimization
- Applications of Path Compression on Balanced Trees
- Finding Dominators in Directed Graphs
- A Simple Algorithm for Global Data Flow Analysis Problems
- Solving path problems on directed graphs.
- Fundamental algorithms