We give a polynomial algorithm to compute shortest paths in weighted undirected graphs with no negative cycles (conservative graphs). We show that our procedure gives a simple algorithm to compute optimal T-joins (and consequently all of their special cases, including weighted matchings). We finally give a direct algorithmic proof for arbitrary weights of a theorem of Sebo characterizing conservative graphs and optimal paths.
Shortest Paths in Conservative Graphs / Rizzi, Romeo; Conforti, Michele. - ELETTRONICO. - (2000), pp. 1-11.
Shortest Paths in Conservative Graphs
Rizzi, Romeo;
2000-01-01
Abstract
We give a polynomial algorithm to compute shortest paths in weighted undirected graphs with no negative cycles (conservative graphs). We show that our procedure gives a simple algorithm to compute optimal T-joins (and consequently all of their special cases, including weighted matchings). We finally give a direct algorithmic proof for arbitrary weights of a theorem of Sebo characterizing conservative graphs and optimal paths.File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
tec53.pdf
accesso aperto
Tipologia:
Versione editoriale (Publisher’s layout)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
234.82 kB
Formato
Adobe PDF
|
234.82 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione