Formulazioni lineari per il problema del taglio minimo

Lo scopo di questa tesi è quello di presentare alcune formulazioni lineari per il problema del taglio minimo. In particolare, dopo aver presentato i programmi lineari più noti per il problema e alcune sue variazioni, verrà analizzato uno studio, presentato nell'articolo "Compacting cuts: A new linear formulation for minimum cut", riguardante una più recente formulazione che si differenzia da tutte quelle presentate nei capitoli precedenti perché richiede O(|V|^2) variabili e O(|V|^3) vincoli, invece che O(|V||E|).