Generation of node lists using segment analysis

Abstract

This paper presents two straightforward algorithms for generating node lists for reducible graphs. The algorithms are much simpler than those of Aho and Ullman [1]. The length of the node list produced by the algorithms given here is bounded above by (d + 1)n, where n is the number of nodes in the graph and d is the number of nodes that are tails of back edges. For realistic programs, however, the algorithms given here produce much shorter node lists, generally of length less than 3n. This paper emphasizes simplicity of the algorithms. © 1980.