CODEWITHSUNDEEP
algorithmdata-structuresgraph-theorygraph-algorithmmax-flow
Wander Nauta
Wander Nauta

Reputation: 19615

Calculating max flow in a generalized network

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?

Upvotes: 3

Views: 790

Answers (2)

user4235730
user4235730

Reputation: 2619

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.)

Upvotes: 0

Mark
Mark

Reputation: 1100

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

Upvotes: 1

Related Questions