Dominators in Linear Time
- 1 January 1999
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 28 (6) , 2117-2132
- https://doi.org/10.1137/s0097539797317263
Abstract
A linear-time algorithm is presented for finding dominators in control flow graphs.Keywords
This publication has 13 references indexed in Scilit:
- Optimal parallel verification of minimum spanning trees in logarithmic timeAlgorithmica, 1997
- Trans-dichotomous algorithms for minimum spanning trees and shortest pathsJournal of Computer and System Sciences, 1994
- Efficiently computing static single assignment form and the control dependence graphACM Transactions on Programming Languages and Systems, 1991
- Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computationCommunications of the ACM, 1988
- A linear-time algorithm for a special case of disjoint set unionJournal of Computer and System Sciences, 1985
- A fast algorithm for finding dominators in a flowgraphACM Transactions on Programming Languages and Systems, 1979
- On Finding Lowest Common Ancestors in TreesSIAM Journal on Computing, 1976
- 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