Testing flow graph reductibility

Research output: Contribution to journalConference articlepeer-review

3 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 0(E logE) time to analyze a graph with E edges, where logx = minCillog11}. The time bound compares favorably with the 0(E log E) bound of a previously known algorithm.

Original languageEnglish (US)
Pages (from-to)96-107
Number of pages12
JournalProceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - Apr 30 1973
Externally publishedYes
Event5th Annual ACM Symposium on Theory of Computing, STOC 1973 - Austin, United States
Duration: Apr 30 1973May 2 1973

All Science Journal Classification (ASJC) codes

  • Software


  • Algorithm
  • Code optimization
  • Complexity
  • Depth-first search
  • Directed graph
  • Flow analysis
  • Flow graph
  • Interval analysis
  • Program optimization
  • Reducibility
  • Set union algorithm
  • Tree


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

Cite this