An improved direct labeling method for the max-flow min-cut computation in large hypergraphs and applications

摘要

Algorithms described so far to solve the maximum flow problem on hypergraphs first necessitate the transformation of these hypergraphs into directed graphs. The resulting maximum flow problem is then solved by standard algorithms. This paper describes a new method that solves the maximum flow problem directly on hypergraphs, leading to both reduced run time and lower memory requirements. We compare our approach with a state-of-the-art algorithm that uses a transformation of the hypergraph into a directed graph and an augmenting path algorithm to compute the maximum flow on this directed graph: the run-time complexity as well as the memory space complexity are reduced by a constant factor. Experimental results on large hypergraphs form VLSI applications show that the run time is reduced, on average, by a factor approximately 2, while memory occupation is reduced, on average, by a factor of 10. This improvement is particularly interesting for very large instances, to be solved in practical applications.