Algoritmos para geração de dígrafos redutíveis

Abstract

This Technical Report describes four algorithmsfor the reducible flow graphs generation. We characterize at first this class of digraphs, enunciating their mais properties and Tarjan's recognition alorithm. We propose two methods for the random eneration: the first one is a slight variant of the reducibility test applied on a digraph randomly generated, deleting the edges which violate the reducibility criteria: the second one, uses a post-order traversal of a partitioning tree. Finally, the subclass of complete (or saturated) reducible flow graphs is also characterized, including two distinct methods for its generation.