Indice
Introduzione………. 1
Capitolo 1 Il problema dei cammini bilanciati in reti acicliche...6
1.1 Formulazione………...………. 6
1.2 Complessità computazionale in tempo………. 7
1.3 Un algoritmo pesudopolinomiale………. 9
1.3.1 Descrizione ……… 9
1.3.2 Complessità computazionale in tempo dell’algoritmo ………….11
1.4 Le varianti arc-disjoint e node-disjoint ………11
1.4.1 Equivalenza delle varianti node-disjoint e arc-disjoint………… 11
1.4.2 Complessità computazionale in tempo………..14
1.4.3 Il caso node-disjoint: numero di livelli costante...………....16
1.4.3.1 Descrizione dell’algoritmo……..………16
1.4.3.2 Complessità computazionale dell’algoritmo ……… .18
1.4.3.3 Il caso di coppie origine-destinazione date……… 18
Capitolo 2 Una famiglia di algoritmi euristici per reti generiche 20
2.1 Grafi di input generici...……… 202.2 Una famiglia di algoritmi euristici...23
2.2.1 Approccio euristico...23
2.2.2 Varianti dell’approccio euristico implementate...24
2.3 Analisi delle colorazioni...25
2.3.1 Equivalenza tra colorazioni...25
2.3.2 Alcune stime probabilistiche...26
Capitolo 3 Aspetti implementativi………29
3.1 Struttura del software... ……….. 29
3.2 Individuazione di un cammino colorful...31
3.3 Rappresentazione dei colori e verifica della proprietà colorful...32
3.4 Scelte implementative per un miglioramento delle performance...34
3.4.1 Approssimazione di U e ricerca binaria...34
3.4.2 Calcolo di una soluzione iniziale: caso coppie origine-destinazione non date...36
3.4.3 Calcolo di una soluzione iniziale: caso coppie origine-destinazione date...37
3.4.4 Scelta delle famiglie di sottografi di GUda analizzare...38
3.4.5 Ordine di analisi dei sottografi...41
3.4.6 Verifica dell’equivalenza di due colorazioni...41
Capitolo 4 Sperimentazioni...………45
4.1 Descrizione del dataset...………..45
4.2 Descrizione di una singola istanza...49
4.3 Parametri delle sperimentazioni... 50
4.4 Analisi del comportamento dell’approccio euristico... 51
4.5 Analisi dei risultati... 52
