A Scalable, Memory-Efficient Algorithm for Minimum Cycle Mean Calculation in Directed Graphs

The concept of minimum cycle mean (MCM) in a directed graph has many applications in the design of circuits and systems. The algorithm by Young, Tarjan, and Orlin (YTO), when implemented with a binary heap, has been reported to be the fastest MCM algorithm in practice even when it has higher asymptotic time complexity than Karp's algorithm. However, as an efficient implementation of YTO relies on data redundancy, its memory usage is higher and could be a prohibitive factor in large size problems. On the other hand, a typical implementation of Karp's algorithm can also be memory hungry, thereby limiting its application to only small size problems. An early termination technique from Hartmann and Orlin (HO) can be directly applied to Karp's algorithm to improve its runtime performance. The early termination also allows memory to be allocated on an on-demand basis, which can reduce the memory requirement of Karp's algorithm. In our evaluation based on graphs constructed from IWLS 2005 benchmark circuits and randomly generated graphs, we empirically observe that the HO algorithm (or Karp's algorithm with early termination technique from the HO algorithm) has much less memory usage than YTO, but it lags behind YTO in runtime performance. We propose several improvements to the early termination technique of the HO algorithm. While further improving its memory advantage over YTO, we significantly improve the runtime performance of the HO algorithm to the extent that the proposed algorithm has runtime performance that is comparable to YTO for circuit-based graphs and for dense randomly generated graphs.

Automated summary

The concept of minimum cycle mean in a directed graph is widely used in circuit and system design. The YTO algorithm, implemented with a binary heap, is reported to be the fastest MCM algorithm, while the Karp algorithm can also be memory hungry. The early termination technique from the HO algorithm improves the runtime performance of Karp's algorithm and reduces its memory requirement.