Algoritmo di Edmonds

In 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 cammini e 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 Jack Edmonds nel 1967. Edmonds ha fornito una prova della sua correttezza utilizzando procedimenti della programmazione lineare. Si tratta di una dimostrazione piuttosto macchinosa e complessa.

Bibliografia

• Y. J. Chu. T. H. Liu: On the Shortest Arborescence of a Directed Graph, Science Sinica, v. 14, (1965), pp. 1396-1400.
• J. Edmonds: Optimum Branchings, J. Res. Nat. Bur. Standards, v. 71B, 1967, pp. 233-240.
• Robert Tarjan: Finding Optimum Branchings, Networks, v.7, 1977, pp.25-35.
• P.M. Camerini, L. Fratta, F. Maffioli: A note on finding optimum branching, Networks, v.9, (1979), pp.309-312.
• Alan Gibbons: Algorithmic Graph Theory, Cambridge University Press, (1985(, ISBN 0-521-28881-9
• H. N. Gabow, Z. Galil, T. Spencer, R. E. Tarjan: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica 6 (1986), 109-122.
• Y. Zhang: Parallel algorithms for minimal spanning trees of directed graphs, Int. J. Parallel Program., 3 (June 1990), pp. 109-122
• T. Magnanti, L. Wolsey: Handbooks in Operational Researh and Management Science: Optimal Trees (1995)

Collegamenti esterni

• The Directed Minimum Spanning Tree Problem Description of the algorithm summarized by Shanchieh Jay Yang, May 2000.

• Edmonds's algorithm ( edmonds-alg ) - An open source implementation of Edmonds's algorithm written in C++ and licensed under the MIT License. This source is using Tarjan's implementation for the dense graph.

• AlgoWiki - Edmonds's algorithm - A public-___domain implementation of Edmonds's algorithm written in Java.