Edmonds's algorithm

From Wikipedia, the free encyclopedia

In graph theory, a branch of mathematics, 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 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.

Contents 1 Conditions 2 Execution 3 References 4 External links

[edit] 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. C_i is a circuit. G₀ = (V₀,E₀) is the original digraph. u_i is a replacement vertex for C_i.

[edit] Execution

1.

2.

3. if BV = V_i, then go to step 14

4. for some vertex and do

begin

5.______

6.______find an edge e = (x,v) such that

7.______if then go to three

end

8.if contains a circuit then

begin

9.______

10._____construct G_i by shrinking C_i to u_i

11._____modify BE, BV and some edge weights

end

12.

13.go to three

14.while do

begin

15._____reconstruct G_{i − 1} and rename some edges in BE

16._____if u_i was a root of an out-tree in BE then

17._____ and

18._____else and

19._____

end

20._____Maximum branching weight

[edit] References

• 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

[edit] External links

• Edmonds's algorithm ( edmonds-alg ) - An open source implementation of Edmonds's algorithm written in C++ and licensed under the MIT License