ACM Transactions on Programming Languages and Systems · 1998 · 64 citations · 23 references
ComputingComputer ScienceAlgorithmsData StructuresParallel ComputingData-flow AnalysisGraph AlgorithmsGraph TheoryNetwork Flow AlgorithmsNetwork FlowsSublinear AlgorithmsConstant-time AlgorithmsDominator Tree ConstructionGraph ProcessingPath CompressionTree Algorithms
We present a new linear-time algorithm to find the immediate dominators of all vertices in a flowgraph. Our algorithm is simpler than previous linear-time algorithms: rather than employ complicated data structures, we combine the use of microtrees and memoization with new observations on a restricted class of path compressions. We have implemented our algorithm, and we report experimental results that show that the constant factors are low. Compared to the standard, slightly superlinear algorithm of Lengauer and Tarjan, which has much less overhead, our algorithm runs 10-20% slower on real flowgraphs of reasonable size and only a few percent slower on very large flowgraphs.
23
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 17K citations
Depth-First Search and Linear Graph Algorithms
Robert E. Tarjan · SIAM Journal on Computing · 1972 · 6K citations
1990 · 3.1K citations