Vai ai contenuti. | Spostati sulla navigazione | Spostati sulla ricerca | Vai al menu | Contatti | Accessibilità

logo del sistema bibliotecario dell'ateneo di padova

Manente, Alessandro (2018) Algoritmi per il problema del flusso massimo in una rete. [Laurea triennale]

Per questo documento il full-text online non disponibile.

Abstract

Il problema del flusso massimo in una rete venne formulato per la prima volta nel 1954 da T. E. Harris e F. S. Ross per la semplificazione del modello del flusso del sistema ferroviario sovietico. Nel 1955, Lester R. Ford, Jr. e Delbert R. Fulkerson pubblicarono il primo algoritmo noto, l'algoritmo di Ford-Fulkerson. Negli anni a venire, vengono ideate varie soluzioni al problema, fra cui le più note sono quelle degli statunitensi Edmonds e Karp (1972) e del sovietico Dinic (1970); un ulteriore algoritmo verrà poi proposto dagli statunitensi Goldberg e Tarjan (1988). Lo scopo di questo lavoro è presentare gli algoritmi sopracitati, dimostrare che questi risolvono il problema in un tempo polinomiale, escluso l'algoritmo di Ford-Fulkerson, e che questi terminano sempre, anche in caso di dati non razionali.

Item Type:Laurea triennale
Corsi di Laurea Triennale:pre 2012- Facoltà di Scienze MM. FF. NN. > Matematica
Subjects:Area 01 - Scienze matematiche e informatiche > MAT/09 Ricerca operativa
Codice ID:61620
Relatore:Di Summa, Marco
Data della tesi:14 November 2018
Biblioteca:Polo di Scienze > Biblioteca di Matematica

Solo per lo Staff dell Archivio: Modifica questo record