2
$\begingroup$

TL;DR: There're lecture notes about a very simple reduction from "maximum flow with edge demands problem to the maximum flow problem. But I can't get the new capacities at the picture: graph

E.g., look at the diagonal: 15 - 0 = 14 (?). From my point of view there're a lot of off-by-one errors.

$\endgroup$
1
$\begingroup$

Those are just typos, as you can confirm by reading the general construction on the previous page ("Intuitively, we construct $G'$ by ...") and applying it to the flow network on the left. Yes, there are multiple off-by-one errors. It happens. Pobody's nerfect.

Incidentally, you might want to read the latest version of his notes, available from http://web.engr.illinois.edu/~jeffe/teaching/algorithms/, rather than the 2009 version you're reading right now (though this particular typo is still present).

$\endgroup$

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.