Lezione 11.2: complessità, corettezza e terminazione dell'algortimo per cammini aumentanti
Aggregazione dei criteri
Algoritmo dei cammini aumentanti: correttezza (dimostrazione del teorema) e terminazione (integralità). L'algoritmo risolve il problema del taglio di capacità minima. Complessità pseudo-polinomiale della versione generale e perché è potenzialmente preoccupante (istanze con "archi grandi ed archi piccoli").