Calculating max flow in a generalized network

Question

I'm trying to find an efficient, publically available algorithm, preferably with implementation, for solving maximum flow in a generalized (non-pure) network with gains. All multipliers, capacities and flow values are non-zero integers.

Does such an algorithm exist, or is this problem not solvable in polynomial time?

Answer 1

Here are some links to some algorithms and some explication:

1. http://en.wikipedia.org/wiki/Edmonds-Karp_algorithm
2. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow
3. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow2

This is my solution for a maximum flow : sorry for the variables name i was young then :) http://infoarena.ro/job_detail/431616?action=view-source
Hope it helped

Answer 2

The first (strongly) polynomial-time algorithm was published by Végh in 2013, and has since been improved by Olver and Végh to a worst-case runtime in O((m + n log n) m n log(n^2 / m)). But I don't know of any public implementation for this algorithm.

The linked papers also contain references to earlier (weakly) polynomial-time algorithms as well as approximate algorithms, some of which may have public implementations. (This older paper by Tardos and Wayne mentions a C++ implementation.)