2
$\begingroup$

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?

$\endgroup$

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.