### Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 355-365 |

Number of pages | 11 |

Journal | Journal of Computer and System Sciences |

Volume | 9 |

Issue number | 3 |

DOIs | |

State | Published - Dec 1974 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics