1
$\begingroup$

To the best of my knowledge, the best algorithm for the minimum s-t cut in a weighted digraph is the Goldberg push-relabel algorithm with $O(n^{2}\sqrt{m})$ time complexity. I'm interested in solving this problem as a separation sub-problem inside a branch and cut algorithm, so I don't always need the optimal solution. Is there a heuristic/approximation/randomized algorithm for the min s-t cut problem with better time complexity?

$\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.