Testing Flow Graph Reducibility
| dc.contributor.author | Tarjan, Robert Endre | en_US |
| dc.date.accessioned | 2007-04-19T19:02:50Z | |
| dc.date.available | 2007-04-19T19:02:50Z | |
| dc.date.issued | 1973-01 | en_US |
| dc.description.abstract | Many problems in program optimizationn 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|\log^{i}x \leq 1\}$. The time bound compares favorably with the $O(E \log E)$ bound of a previously known algorithm. | en_US |
| dc.format.extent | 1590908 bytes | |
| dc.format.extent | 531993 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.citation | http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR73-159 | en_US |
| dc.identifier.uri | https://hdl.handle.net/1813/6008 | |
| dc.language.iso | en_US | en_US |
| dc.publisher | Cornell University | en_US |
| dc.subject | computer science | en_US |
| dc.subject | technical report | en_US |
| dc.title | Testing Flow Graph Reducibility | en_US |
| dc.type | technical report | en_US |