In graph theory, Edmonds' algorithm or Chu–Liu/Edmonds' algorithm is an algorithm for finding a spanning arborescence of minimum weight (sometimes called an optimum branching).
[1] It is the directed analog of the minimum spanning tree problem.
The algorithm was proposed independently first by Yoeng-Jin Chu and Tseng-Hong Liu (1965) and then by Jack Edmonds (1967).
The algorithm takes as input a directed graph
is the set of directed edges, a distinguished vertex
called the root, and a real-valued weight
It returns a spanning arborescence
of minimum weight, where the weight of an arborescence is defined to be the sum of its edge weights,
The algorithm has a recursive description.
denote the function which returns a spanning arborescence rooted at
We may also replace any set of parallel edges (edges between the same pair of vertices in the same direction) by a single edge with weight equal to the minimum of the weights of these parallel edges.
other than the root, find the edge incoming to
of lowest weight (with ties broken arbitrarily).
Denote the source of this edge by
Arbitrarily choose one of these cycles and call it
We now define a new weighted directed graph
Now find a minimum spanning arborescence
is a spanning arborescence, each vertex has exactly one incoming edge.
be the unique incoming edge to
Mark each remaining edge in
, mark its corresponding edge in
to be the set of marked edges, which form a minimum spanning arborescence.
having strictly fewer vertices than
for a single-vertex graph is trivial (it is just
itself), so the recursive algorithm is guaranteed to terminate.
The running time of this algorithm is
A faster implementation of the algorithm due to Robert Tarjan runs in time
for dense graphs.
This is as fast as Prim's algorithm for an undirected minimum spanning tree.
In 1986, Gabow, Galil, Spencer, and Tarjan produced a faster implementation, with running time