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(n~2 m log(n~2 /m)) algorithm for finding a maximum cycle packing in any weighted reducible flow graph with n vertices and m arcs.