• programmazione dinamica
• euristica
• algoritmo pseudopolinomiale
• cammini arc-disjoint
• cammini node-disjoint
• bilanciamento

Nel primo capitolo viene fornita una formulazione del problema dei cammini bilanciati nel caso di grafi aciclici, si analizza la complessità computazionale in tempo di tale problema e si descrive con completezza un algoritmo di risoluzione. Nel capitolo si affrontano e si analizzano anche le versioni node-disjoint e arc-disjoint del problema, e si descrive come adattare l’algoritmo precedentemente descritto per poter risolvere le due varianti del problema per alcuni casi speciali.
Nel secondo capitolo si presenta la generalizzazione del problema al caso di grafi di input generici. Si mostra come l’algoritmo per reti acicliche, descritto nel primo capitolo, possa essere adattato al caso in cui il grafo di input contenga cicli e si mostra come tale approccio possa essere utilizzato per progettare una famiglia di algoritmi euristici che guidi efficientemente nella ricerca di soluzioni di buona qualità.
Nel terzo capitolo innanzitutto si descrive il software che implementa l’approccio euristico proposto e successivamente si riportano le principali scelte implementative effettuate nelle fasi di progettazione e realizzazione del software.
Nei capitoli successivi si descrive il dataset utilizzato per effettuare le sperimentazioni e si fa un’analisi dei risultati ottenuti.