Definitions

# Edmonds's algorithm

In graph theory, a branch of mathematics, Edmonds's algorithm or Chu–Liu/Edmonds's algorithm is an algorithm for finding a maximum or minimum branchings. When nodes are connected by weighted edges that are directed, a minimum spanning tree algorithm cannot be used. Instead an optimum branching algorithm should be applied using the algorithm proposed independently first by Chu and Liu (1965) and then by Edmonds (1967). To find a maximum path length, the largest edge value is found and connected between the two nodes, then the next largest value, and so on. If an edge creates a loop, it is erased. A minimum path length is found by starting from the smallest value.

## Conditions

Let BV be a vertex bucket and BE be an edge bucket. Let v be a vertex and e be an edge of maximum positive weight that is incident to v. Ci is a circuit. G0 = (V0,E0) is the original digraph. ui is a replacement vertex for Ci.

## Execution

``` $BV leftarrow BE leftarrow varnothing$ i=0 A: if $BV = V_i$ then goto B for some vertex $v notin BV$ and $v in V_i$ { $BV leftarrow BV cup lbrace vrbrace$ find an edge $e = \left(x,v\right)$ such that w(e) = max{ w(w,y)|(w,y) $in$ Ei} if w(e) ≤ 0 then goto A } if $BE cup lbrace erbrace$ contains a circuit { i=i+1 construct $G_i$ by shrinking $C_i$ to $u_i$ modify BE, BV and some edge weights } $BV leftarrow BE cup \left\{e\right\}$ goto A B: while i ≠ 0 { reconstruct $G_\left\{i-1\right\}$ and rename some edges in BE if $u_i$ was a root of an out-tree in BE { $BE leftarrow BE cup lbrace e|e in C_i$ and $e ne e_0^irbrace$ }else{ $BE leftarrow BE cup lbrace e|e in C_i$ and $e ne tilde\left\{e\right\}_irbrace$ } i=i-1 } Maximum branching weight = $sum_\left\{e in BE\right\} w\left(e\right)$ ```

To author: modify BE, BV and some edge weights - how?
`$u_i$` - what is `$u_i$`?

## References

• Y. J. Chu and T. H. Liu, "On the Shortest Arborescence of a Directed Graph", Science Sinica, vol. 14, 1965, pp. 1396-1400.
• J. Edmonds, “Optimum Branchings”, J. Res. Nat. Bur. Standards, vol. 71B, 1967, pp. 233-240.
• Alan Gibbons Algorithmic Graph Theory, Cambridge University press, 1985 ISBN: 0-521-28881-9