As you said: the Knuth/Plass algorithmn does not reduce or even detect rivers. Detecting rivers can be done in linear time, but reducing is very likely to put the algorithm in a higher time complexity class (which is almost linear with input length for the normal algorithm!).
