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.
2000
Trento, Italia
Università degli Studi di Trento. DEPARTMENT OF INFORMATION AND COMMUNICATION TECHNOLOGY
Shortest Paths in Conservative Graphs / Rizzi, Romeo; Conforti, Michele. - ELETTRONICO. - (2000), pp. 1-11.
Rizzi, Romeo; Conforti, Michele
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/358471
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact