Algoritmi per problemi di partizione ottima di grafi
In questa ricerca intendiamo studiare alcuni problemi di partizione ottima di grafi. Si tratta di problemi che nel caso generale sono difficili da risolvere (NP-hard) e la loro soluzione richiede l'utilizzo di algoritmi di tipo enumerativo oppure di algoritmi euristici che però non garantiscono l'ottimalità della soluzione fornita.
Considereremo in particolare problemi di partizione connessa e di b-colorazione di grafi arbitrari per i quali vogliamo proporre formulazioni come problemi di Programmazione Lineare a variabili 0-1 su cui mettere a punto algoritmi di Branch and Cut e Branch and Price. La validità dei modelli e degli algoritmi verrà verificata con adeguate sperimentazioni.
Ci proponiamo inoltre di studiare la complessità computazionale dei problemi di equipartizione su grafi outerplanar.
Infine intendiamo proporre algoritmi efficienti per il problema di calcolare la vitalità di un arco rispetto al problema del massimo flusso-minimo taglio.