In questa tesi si propone di classificare la potenza di algoritmi in base alla complessità dei problemi che essi possono risolvere durante il loro processo di esecuzione. In particolare Si mostra che il Network Simplex Method e il Successive Shortest Path Algorithm sono NP-potenti, ossia che entrambi possono essere utilizzati per risolvere qualsiasi problema in NP.
NP-potenza di algoritmi per il problema di flusso di costo minimo
GIOMO, STEFANO
2022/2023
Abstract
In questa tesi si propone di classificare la potenza di algoritmi in base alla complessità dei problemi che essi possono risolvere durante il loro processo di esecuzione. In particolare Si mostra che il Network Simplex Method e il Successive Shortest Path Algorithm sono NP-potenti, ossia che entrambi possono essere utilizzati per risolvere qualsiasi problema in NP.File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
NP-potenza di algoritmi per il problema del flusso di costo minimo.pdf
accesso riservato
Dimensione
399.39 kB
Formato
Adobe PDF
|
399.39 kB | Adobe PDF |
The text of this website © Università degli studi di Padova. Full Text are published under a non-exclusive license. Metadata are under a CC0 License
Utilizza questo identificativo per citare o creare un link a questo documento:
https://hdl.handle.net/20.500.12608/61307