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.
Problemi di partizione connessa di grafi
Il tema considerato si innesta su due filoni di ricerca che in questo periodo destano molto interesse: da una parte, i problemi di programmazione lineare intera per i quali negli ultimi anni è stato possibile migliorare le formulazioni e le implementazioni permettendo la soluzione di problemi di dimensioni sempre maggiori; dall'altra, i problemi di partizione di grafi che, come già detto, hanno applicazioni in diversi settori molti dei quali legati al disegno di reti e al trattamento delle informazioni.
Per alcuni problemi, come l'equipartizione di grafi, intendiamo valutare quali tra le formulazioni già proposte in letteratura per altri problemi di partizione connessa forniscono buoni risultati e, eventualmente, proporre nuove formulazioni.
I problemi di equipartizione di grafi sono risolvibili in tempo polinomiale su alberi e sono NP-hard su grafi serie paralleli, mentre ancora non si conosce la complessità computazionale per i grafi outerplanar, che sono un caso particolare dei grafi serie paralleli. Nella nostra ricerca ci proponiamo di studiare questo problema.
Problema della b-colorazione di un grafo
La metodologia proposta risulta innovativa e potenzialmente efficiente per molteplici aspetti.
Anzitutto, ad oggi sono pochi i contributi in letteratura inerenti all'applicazione di metodi esatti che sfruttano la Generazione Colonne integrata in uno schema di Branch-and-Bound per la risoluzione di problemi di coloring.
In secondo luogo, siamo certi dell'efficacia del metodo di Generazione Colonne per la risoluzione del problema classico di colorazione di grafi, in quanto già sfruttato da Mehrotra e Trick nel 1996. Siamo quindi convinti che tale metodologia possa essere generalizzata per la risoluzione di diversi problemi di colorazione di grafi e continuare a risultare efficace, fornendo la possibilità di risolvere problemi di dimensioni sempre maggiori.
Vitalità degli archi di un grafo rispetto al flusso massimo-minimo taglio
Il problema della determinazione della vitalità degli archi di un grafo con algoritmi efficienti è stato ben studiato in letteratura per il problema del cammino minimo e in questa ricerca intendiamo individuare algoritmi efficienti per la vitalità degli archi rispetto al problema del flusso massimo.