News for hackers. Stuff that matters.
Re:New algorithm can dramatically streamline solutions to th... by tubbzor on Wednesday January 08, 2014 @08:56AM (#7023426)
You are right! Edmonds-karp was developed (really just a modified Ford-Faulkerson approach with a BFS as opposed to a random augmenting path...but we'll give it to him), yielding an O(ve^2) algorithm. A russian (soviet) mathematician named Dinic nearly simultaneously, and independently, developed an O(ev^2) algorithm which we can see beats Edmonds-karp as edge density grows.

There are no comments on this comment yet.