2
$\begingroup$

Could you, please, suggest a maximum flow algorithm for a graph with floating-point weights and the number of edges approximately equal to the number of vertices? I.e. O(V^3) algorithms take too much time, but O(E^2) algorithms are much more preferable. More specifically, you can assume V~=1M and E~=10M where M stands for millions.

$\endgroup$
0
$\begingroup$

Orlin's algorithm can solve max flow in sparse graphs in $O(|V| |E|)$ time. See

Max flows in O(nm) time, or better. James B. Orlin. STOC 2013.

You'll have to decide whether the potential speedup is worth the time to implement it, as I believe the algorithm is quite complex. I don't know whether the algorithm is better in practice.

Perhaps someone else will have better suggestions for you.

$\endgroup$
4
  • $\begingroup$ Orlin's algorithm seems more like a theoretical curiosity than a practical algorithm. Sleator & Tarjan's implementation of Dinic's algorithm works in $O(|V| |E| \log |V|)$ time and was published in 1982. $\endgroup$ – Laakeri Dec 26 '19 at 23:49
  • $\begingroup$ @Laakeri, I didn't know about that -- can you post a full answer with more information about that? $\endgroup$ – D.W. Dec 27 '19 at 3:38
  • $\begingroup$ Are you sure these algorithms work with floating-point weights? Is the implementation available publicly? $\endgroup$ – Serge Rogatch Dec 27 '19 at 8:29
  • $\begingroup$ @SergeRogatch, I believe Orlin's algorithm works with non-integral weights but I haven't confirmed it. I am not aware of any publicly available implementation. $\endgroup$ – D.W. Dec 27 '19 at 8:34

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.