An efficient algorithm for finding maximum cycle packings in reducible flow graphs

Reducible flow graphs occur naturally in connection with flow-charts of computer programs and are used extensively for code optimization and global data flow analysis. In this paper we present an O(n2m log (n 2/m)) algorithm for finding a maximum cycle packing in any weighted reducible flow graph with n vertices and m arcs. © Springer-Verlag 2004.postprin