A Fast Algorithm for finding Dominators in a Flow Graph,

Abstract

This paper presents a fast algorithm for finding dominators in a flow graph. 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 sophisticated implementation runs in O(M alpha (m, n)) time, where alpha(m, n) is a functional inverse of Ackermann's function. Both versions of the algorithm were implemented in Algol W, 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. The fast algorithm beat the straightforward algorithm and the bit vector algorithm on all but the smallest graphs tests.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1978
Accession Number
ADA054144

Entities

People

  • Robert Tarjan
  • Thomas Lengauer

Organizations

  • Stanford University

Tags

Communities of Interest

  • Advanced Electronics

DTIC Thesaurus Topics

  • Algorithms
  • Assembly Languages
  • Compression
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Instructions
  • Mathematics
  • Military Research
  • Object Code
  • Schools
  • United States
  • United States Government
  • Universities

Fields of Study

  • Computer science

Readers

  • Computer Science.
  • Graph Algorithms and Convex Optimization.