Изменения

Работа с максимальным потоком в расширенной сети занимает <tex>O (m n^3)</tex> шагов, проверка может быть сделана с такой же скоростью. Для решения <tex>Q|\mid pmtn; r_{i}|\mid 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 | \mid pmtn; r_i | \mid C_{max}</tex> представляет собой частный случай <tex>Q | \mid pmtn; r_i | \mid L_{max}</tex>, и может быть решена более эффективно. Labetoulle, Lawler, Lenstra, и Rinnooy Kan разработали алгоритм работающий за <tex> O(n log(n) + mn) </tex> специально для этого случая.

|statement= Задача <tex>Q | \mid pmtn | \mid L_{max}</tex> может быть решена за <tex> O(n log(n) + mn) </tex> шагов.

Решение <tex>Q | \mid pmtn; r_i | \mid C_{max}</tex> эквивалентно нахождению наименьшего <tex>T \ge 0</tex>, такого, что задача с допустимым временным интервалом <tex>[r_i, T] (i = 1, . . . , n)</tex> имеет решение.

С другой стороны, решение <tex>Q | \mid pmtn | \mid L_{max}</tex> эквивалентно нахождению такого наименьшего <tex>T \ge 0</tex>, такого, что задача с временным интервалом <tex>[0, d_i + T]</tex> или <tex>[−T, d_i]</tex> имеет решение.

Таким образом, задачи <tex>Q | \mid pmtn; r_i | \mid Cmax</tex> и <tex>Q | \mid pmtn | \mid L_{max}</tex> симметричны.