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). 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).

Algorithm

Description

called the root. It returns a spanning arborescence.

. 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.

.

is "contracted" into one node as follows:

plus a new.

• .

• .

• .

it corresponds to.

to be the set of marked edges, which form a minimum spanning arborescence.

itself), so the recursive algorithm is guaranteed to terminate.

Running time

. A faster implementation of the algorithm due to Robert Tarjan for sparse graphs for dense graphs. This is as fast as Prim's algorithm for an undirected minimum spanning tree. In 1986, Gabow, Galil, Spencer, and Tarjan.

References

External links

• Edmonds's algorithm ( edmonds-alg ) – An 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.

• NetworkX, a python library distributed under BSD, has an implementation of Edmonds' Algorithm.

• (spanning-forest-builder 0.0.2) – Library for constructing oriented forests of minimum weight.