Edmonds' algorithm
Algoritmo de Edmond
- Date
- 1965 (Chu-Liu) / 1967 (Edmonds) · confidence high
- Place
- Washington, D.C., United States
- Credited to
- Yoeng-Jin Chu, Tseng-Hong Liu y Jack Edmonds
- Field
- Knowledge & symbols
What it is
An algorithm that finds the minimum-weight spanning arborescence in a directed graph, proposed independently by Yoeng-Jin Chu and Tseng-Hong Liu and later by Jack Edmonds, the directed analog of the minimum spanning tree.
What it led to
- the basis for optimization algorithms on directed networks
- applied in computational biology and dependency parsing
- extended to network flow problems