MICHELE CONFORTI, ROMEO RIZZI,
Shortest Paths in Conservative Graphs,
accepted by Discrete Mathematics .ps filedescrizione:
L'algoritmo di Ford e Fulkerson
computa i cammini minimi in un grafo orientato
con pesi razionali sugli archi,
accertando al contempo l'assenza di cicli di peso totale
negativo.
Ma quando il grafo non é orientato,
nessun algoritmo specifico era noto per lo stesso problema,
che doveva venir risolto con tecniche di matching.
In effetti queste tecniche mostravano come
il problema fosse di fatto piú difficile che non nel caso diretto.
In questo lavoro abbiamo definito due operazioni elementari
che, combinate, riescono a ridurre il grafo dato in input
ad un nodo singolo
a meno che un'anomalia non venga riscontrata
in una certa fase del processo di riduzione.
Se il grafo si riduce ad un nodo singolo
allora ne deduciamo che esso non conteneva
cicli negativi ed i cammini correntemente impugnati sono ottimi.
Se un'anomalia é riscontrata,
allora, procedendo a ritroso,
o scopriamo di poter migliorare uno dei cammini correntemente considerati,
o reperiamo un ciclo negativo.
Ció ci consente di ottenere
un algoritmo specifico
per il problema dei cammini minimi su grafi non diretti
e conservativi (= senza cicli negativi).
L'algoritmo puó essere
considerato come un algoritmo alternativo
per problemi di matching in generale.
Inoltre tramite esso é possibile
fornire dimostrazione algoritmica
di varie proprietá strutturali
di grafi conservativi e cammini minimi.
