Talk:Edmonds–Karp algorithm: Difference between revisions

Revision as of 08:46, 25 October 2007

Revision as of 14:52, 1 October 2008

Line 53:

At the end of the example it says that the minimal cut partitions the nodes into ''"sets {A,B,C,E} and {D,F,G}, with the capacity c(A,D) + c(C,D) + c(E,G) = 3 + 1 + 1 = 5."'' But isn't the capacity here missing edge (D,E) with c(D,E) = 2 ? The capacity of the cut would then be 7 instead of 5. <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/134.60.236.119|134.60.236.119]] ([[User talk:134.60.236.119|talk]]) 15:15, 23 October 2007 (UTC)</small><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->

You state that "...and independently by Jack Edmonds and Richard Karp in 1972 (discovered earlier).". Well, that is usual in any science. Did anybody ask Dinic at what point in time he discovered the algorithm that is attributed to Edmonds and Karp? If not, then the remark "(discovered earlier)" should be removed.