Abstract
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(n2/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.
Similar content being viewed by others
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chen, X., Zang, W. An Efficient Algorithm for Finding Maximum Cycle Packings in Reducible Flow Graphs. Algorithmica 44, 195–211 (2006). https://doi.org/10.1007/s00453-005-1174-x
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-005-1174-x