Testing flow graph reducibility

Research output: Contribution to journalArticlepeer-review

115 Scopus citations


Many problems in program optimization have been solved by applying a technique called interval analysis to the flow graph of the program. A flow graph which is susceptible to this type of analysis is called reducible. This paper describes an algorithm for testing whether a flow graph is reducible. The algorithm uses depth-first search to reveal the structure of the flow graph and a good method for computing disjoint set unions to determine reducibility from the search information. When the algorithm is implemented on a random access computer, it requires O(E log*E) time to analyze a graph with E edges, where log*x=min{i{norm of matrix}log(i)x≤1}. The time bound compares favorably with the O(E log E) bound of a previously known algorithm.

Original languageEnglish (US)
Pages (from-to)355-365
Number of pages11
JournalJournal of Computer and System Sciences
Issue number3
StatePublished - Dec 1974
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science
  • Applied Mathematics
  • Computer Networks and Communications
  • Computational Theory and Mathematics


Dive into the research topics of 'Testing flow graph reducibility'. Together they form a unique fingerprint.

Cite this