Изменения
→Время работы
Из-за максимального потока в расширенной сети могут быть рассчитаны в <tex>O (m n^3)</tex> шагов, возможность проверки может быть сделано с такой же сложности. Для решения задачи <tex>Q|pmtn; r_{i}|L_{max}</tex> мы используем бинарный поиск. Получается алгоритм со сложностью <tex>O (mn^3(log(n) + log (\max\limits_{i=1}^{n} p_i)) </tex>, потому что <tex>L_{max}</tex>, ограничен <tex>n \max\limits_{i=1}^{n}p_i</tex>, при <tex>s_1 = 1</tex>.
<tex>Q | pmtn; ri | Cmax</tex> представляет собой частный случай <tex>Q | pmtn; ri | Lmax</tex>, и может быть решена более эффективно. Labetoulle, Lawler, Lenstra, and и Rinnooy Kan разработали алгоритм работающий за <tex> O(n log(n) + mn) </tex> специально для этого случая.
{{Утверждение
|statement= Задача <tex>Q | pmtn | Lmax</tex> может быть решена за <tex> O(n log(n) + mn) </tex> шагов.
