What would be the best algorithm to use for finding max-flow/min-cut on a directed, acyclic graph with integer flows, capacities, and vertex demands? I've been thinking Dinic's Algorithm would be best (especially in terms of implementation as a student), but wasn't sure if there's something more specialized that would work better.

My network has a few large 'supply' nodes, many small 'demand' nodes, and some 'transition' nodes, with each set being bipartite from one another. Because of this, I believe it would be faster to initialize with a feasible flow and then augment to optimal instead of pushing flow until demands are satisfied. Thoughts?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.