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

Reducible flow graphs occur naturally in connection with flowcharts of computer programs and are used extensively for code optimization and global data flow analysis. In this paper we present an O(n2 log(n 2/m)) algorithm for finding a maximum cycle packing in any weighted reducible flow graph with n vertices and m arcs; our algorithm heavily relies on Ramachandran's earlier work concerning reducible flow graphs. © 2005 Springer Science + Business Media, Inc.link_to_subscribed_fulltex