Element (category theory)

2013-08-04T11:17:38Z

78.63.225.128: typo

{{graph search algorithm}}
{{about|the optimum branching algorithm|the maximum matching algorithm|Blossom algorithm}}

In [[graph theory]], a branch of mathematics, '''Edmonds' algorithm''' or '''Chu–Liu/Edmonds' algorithm''' is an [[algorithm]] for finding a maximum or minimum ''optimum branchings''. This is similar to the [[minimum spanning tree]] problem which concerns undirected graphs. However, when nodes are connected by weighted edges that are [[Directed graph|directed]], a [[minimum spanning tree]] algorithm cannot be used.

The optimum branching algorithm was proposed independently first by Yoeng-jin Chu and Tseng-hong Liu (1965) and then by [[Jack Edmonds|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.

==Running time==
The running time of this algorithm is <math>O(EV)</math>. A faster implementation of the algorithm due to [[Robert Tarjan]] runs in time <math>O(E \log V)</math> for [[sparse graph]]s and <math>O(V^2)</math> 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 <math>O(E + V \log V)</math>.

==Algorithm==
===Description===
The algorithm has a conceptual recursive description. We will denote by <math>f</math> the function which, given a weighted directed graph <math>D</math> with a distinguished vertex <math>r</math> called the ''root'', returns a spanning tree rooted at <math>r</math> of minimal cost.

The precise description is as follows. Given a weighted directed graph <math>D</math> with root <math>r</math> we first 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 <math>v</math> other than the root, mark an (arbitrarily chosen) incoming edge of lowest cost. Denote the other endpoint of this edge by <math>\pi(v)</math>. The edge is now denoted as <math>(\pi(v),v)</math> with associated cost <math>w(\pi(v),v)</math>. If the marked edges form an SRT ([[Shortest path tree|Shortest Route Tree]]), <math>f(D)</math> is defined to be this SRT. Otherwise, the set of marked edges form at least one cycle. Call (an arbitrarily chosen) one of these cycles <math>C</math>. We now define a weighted directed graph <math>D^\prime</math> having a root <math>r^\prime</math> as follows. The nodes of <math>D^\prime</math> are the nodes of <math>D</math> not in <math>C</math> plus a ''new'' node denoted <math>v_C</math>.

If <math>(u,v)</math> is an edge in <math>D</math> with <math>u\notin C</math> and <math>v\in C</math>, then include in <math>D^\prime</math> the edge <math>e = (u, v_C)</math>, and define <math>w(e) = w(u,v) - w(\pi(v),v)</math>.

If <math>(u,v)</math> is an edge in <math>D</math> with <math>u\in C</math> and <math>v\notin C</math>, then include in <math>D^\prime</math> the edge <math>e = (v_C, v)</math>, and define <math>w(e) = w(u,v) </math>.

If <math>(u,v)</math> is an edge in <math>D</math> with <math>u\notin C</math> and <math>v\notin C</math>, then include in <math>D^\prime</math> the edge <math>e = (u, v)</math>, and define <math>w(e) = w(u,v) </math>.

We include no other edges in <math>D^\prime</math>.

The root <math>r^\prime</math> of <math>D^\prime</math> is simply the root <math>r</math> in <math>D</math>.

Using a call to <math>f(D^\prime)</math>, find an SRT of <math>D^\prime</math>. First, mark in <math> D </math> all shared edges with <math> D^\prime</math> that are marked in the SRT of <math>D^\prime</math>. Also, mark in <math> D </math> all the edges in <math> C </math>. Now, suppose that in the SRT of <math> D^\prime</math>, the (unique) incoming edge at <math>v_C</math> is <math>(u, v_C)</math>. This edge comes from some pair <math>(u,v)</math> with <math>u\notin C</math> and <math>v\in C</math>. Unmark <math>(\pi(v),v)</math> and mark <math>(u,v)</math>. Also, for each marked <math>(v_C,v)</math> in the SRT of <math> D^\prime</math> and coming from an edge <math> (u,v) </math> in <math> D </math> with <math> u\in C</math> and <math> v\notin C</math>, mark the edge <math> (u,v)</math>. Now the set of marked edges do form an SRT, which we define to be the value of <math>f(D)</math>.

Observe that <math>f(D)</math> is defined in terms of <math>f(D^\prime)</math> for weighted directed rooted graphs <math>D^\prime</math> having strictly fewer vertices than <math>D</math>, and finding <math>f(D)</math> for a single-vertex graph is trivial.

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

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

==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.
* [[Robert Tarjan|R. E. Tarjan]], "Finding Optimum Branchings", Networks, v.7, 1977, pp. 25–35.
* P.M. Camerini, L. Fratta, and F. Maffioli, "A note on finding optimum branchings", Networks, v.9, 1979, pp. 309–312.
* Alan Gibbons ''Algorithmic Graph Theory,'' Cambridge University press, 1985 ISBN 0-521-28881-9
* H. N. Gabow, Z. Galil, T. Spencer, and R. E. Tarjan, “Efficient algorithms for finding minimum spanning trees in undirected and directed graphs,” Combinatorica 6 (1986), 109-122.

== External links ==
*[http://www.ce.rit.edu/~sjyeec/dmst.html The Directed Minimum Spanning Tree Problem ] Description of the algorithm summarized by Shanchieh Jay Yang, May 2000.
*[http://edmonds-alg.sourceforge.net/ Edmonds's algorithm ( edmonds-alg )] – An [[open source]] 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.

[[Category:Graph algorithms]]

formulasearchengine - User contributions [en]

Element (category theory)