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

edit

Description

edit

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

  • If   is an edge in   with   and   (an edge coming into the cycle), then include in   a new edge  , and define  .
  • If   is an edge in   with   and   (an edge going away from the cycle), then include in   a new edge  , and define  .
  • If   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

edit

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  .

References

edit
  • Chu, Yeong-Jin; Liu, Tseng-Hong (1965), "On the Shortest Arborescence of a Directed Graph" (PDF), Scientia Sinica, XIV (10): 1396–1400
  • Edmonds, J. (1967), "Optimum Branchings", Journal of Research of the National Bureau of Standards Section B, 71B (4): 233–240, doi:10.6028/jres.071b.032
  • Tarjan, R. E. (1977), "Finding Optimum Branchings", Networks, 7: 25–35, doi:10.1002/net.3230070103
  • Camerini, P.M.; Fratta, L.; Maffioli, F. (1979), "A note on finding optimum branchings", Networks, 9 (4): 309–312, doi:10.1002/net.3230090403
  • Gibbons, Alan (1985), Algorithmic Graph Theory, Cambridge University press, ISBN 0-521-28881-9
  • Gabow, H. N.; Galil, Z.; Spencer, T.; Tarjan, R. E. (1986), "Efficient algorithms for finding minimum spanning trees in undirected and directed graphs", Combinatorica, 6 (2): 109–122, doi:10.1007/bf02579168, S2CID 35618095
edit