1
$\begingroup$

I am aware that the problem has been discussed here more than once. However, I need to find the maximum number K of vertex-disjoint paths in a directed graph with a running time of |V| x |E|.

I know the algorithm of transforming each vertex into v_in, v_out and adding an edge with capacity 1 from v_in to v_out and for each pair of vertices (u,v) add an edge with capacity 1 from u_out to v_in and then compute the max flow in this network. However, after my calculations this algorithm takes O(E) preprocessing + O(VE^2) or O(V^2E) for max flow. Am I doing something wrong?

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