Algoritmo di Edmonds

Nella teoria dei grafi l'algoritmo di Edmonds, chiamato anche algoritmo di Chu-Liu-Edmonds, è utilizzato per determinare, a partire da un dato digrafo pesato e fortemente connesso, un suo sottoalbero orientato di peso minimo e avente assegnata radice. L'algoritmo individua cioè un sottoinsieme degli archi del dato digrafo che costituisca un albero tale che ogni coppia dei nodi presi in considerazione sia connessa attraverso un cammino orientato e tale che il peso totale degli archi individuati risulti minimo. Una prevedibile variante dell'algoritmo ricerca il sottoalbero orientato di peso massimo. Questo algoritmo è stato sviluppato in modo indipendente da Chu e Liu nel 1965 e da nel 1967. Edmonds ha fornito una dimostrazione della sua correttezza, piuttosto macchinosa e complessa, utilizzando procedimenti della programmazione lineare.