Edmonds' algorithm explained
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
The algorithm takes as input a directed graph
where
is the set of nodes and
is the set of directed edges, a distinguished vertex
called the
root, and a real-valued weight
for each edge
.It returns a spanning
arborescence
rooted at
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.Let
denote the function which returns a spanning arborescence rooted at
of minimum weight.We first remove any edge from
whose destination is
.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.
Now, for each node
other than the root, find the edge incoming to
of lowest weight (with ties broken arbitrarily).Denote the source of this edge by
.If the set of edges
P=\{(\pi(v),v)\midv\inV\setminus\{r\}\}
does not contain any cycles, then
.
Otherwise,
contains at least one cycle.Arbitrarily choose one of these cycles and call it
.We now define a new weighted directed graph
D\prime=\langleV\prime,E\prime\rangle
in which the cycle
is "contracted" into one node as follows:
The nodes of
are the nodes of
not in
plus a
new node denoted
.
is an edge in
with
and
(an edge coming into the cycle), then include in
a new edge
, and define
w\prime(e)=w(u,v)-w(\pi(v),v)
.
is an edge in
with
and
(an edge going away from the cycle), then include in
a new edge
, and define
.
is an edge in
with
and
(an edge unrelated to the cycle), then include in
a new edge
, and define
.
For each edge in
, we remember which edge in
it corresponds to.
Now find a minimum spanning arborescence
of
using a call to
.Since
is a spanning arborescence, each vertex has exactly one incoming edge.Let
be the unique incoming edge to
in
.This edge corresponds to an edge
with
.Remove the edge
from
, breaking the cycle.Mark each remaining edge in
.For each edge in
, mark its corresponding edge in
.Now we define
to be the set of marked edges, which form a minimum spanning arborescence.
Observe that
is defined in terms of
, with
having strictly fewer vertices than
. Finding
for a single-vertex graph is trivial (it is just
itself), so the recursive algorithm is guaranteed to terminate.
Running time
The running time of this algorithm is
. A faster implementation of the algorithm due to
Robert Tarjan runs in time
for
sparse graphs and
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
.
External links
