imported>DanilaBudylyov: /* External links */

2025-01-23T15:31:24Z

External links

New page

{{Short description|Algorithm for the directed version of the minimum spanning tree problem}}
{{about|the optimum branching algorithm|the maximum matching algorithm|Blossom algorithm}}

In [[graph theory]], '''Edmonds' algorithm''' or '''Chu–Liu/Edmonds' algorithm''' is an [[algorithm]] for finding a [[spanning subgraph|spanning]] [[Arborescence (graph theory)|arborescence]] of minimum weight (sometimes called an ''optimum branching'').<ref> The algorithm is applicable to finding a minimum spanning forest with given roots. However, when searching for the minimum spanning forest among all <math>k</math>-component spanning forests, a multiplier arises in the complexity of the algorithm
<math>C_V^k</math>, corresponding to the choice of a subset of vertices designated as roots. This makes it unsuitable for such a task. Even when constructing a minimum spanning tree, regardless of the root, the algorithm must be used
<math>V</math> times, sequentially assigning each vertex as the root. An efficient algorithm for finding minimum spanning forests that solves the root assignment problem is presented in (https://link.springer.com/article/10.1007/s10958-023-06666-w).
It builds a sequence of minimal <math>k</math>-component spanning forests for all <math>k</math> up to the minimum spanning tree. The Chu-Liu/Edmonds algorithm is a component of it. </ref>
It is the [[Directed graph|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 <math>D = \langle V, E \rangle</math> where <math>V</math> is the set of nodes and <math>E</math> is the set of directed edges, a distinguished vertex <math>r \in V</math> called the ''root'', and a real-valued weight <math>w(e)</math> for each edge <math>e \in E</math>.
It returns a spanning [[Arborescence (graph theory)|arborescence]] <math>A</math> rooted at <math>r</math> of minimum weight, where the weight of an arborescence is defined to be the sum of its edge weights, <math>w(A) = \sum_{e \in A}{w(e)}</math>.

The algorithm has a recursive description.
Let <math>f(D, r, w)</math> denote the function which returns a spanning arborescence rooted at <math>r</math> of minimum weight.
We first remove any edge from <math>E</math> whose destination is <math>r</math>.
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 <math>v</math> other than the root, find the edge incoming to <math>v</math> of lowest weight (with ties broken arbitrarily).
Denote the source of this edge by <math>\pi(v)</math>.
If the set of edges <math>P = \{(\pi(v),v) \mid v \in V \setminus \{ r \} \}</math> does not contain any cycles, then <math>f(D,r,w) = P</math>.

Otherwise, <math>P</math> contains at least one cycle.
Arbitrarily choose one of these cycles and call it <math>C</math>.
We now define a new weighted directed graph <math>D^\prime = \langle V^\prime, E^\prime \rangle</math> in which the cycle <math>C</math> is "contracted" into one node as follows:

The nodes of <math>V^\prime</math> are the nodes of <math>V</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>E</math> with <math>u\notin C</math> and <math>v\in C</math> (an edge coming into the cycle), then include in <math>E^\prime</math> a new edge <math>e = (u, v_C)</math>, and define <math>w^\prime(e) = w(u,v) - w(\pi(v),v)</math>.
* If <math>(u,v)</math> is an edge in <math>E</math> with <math>u\in C</math> and <math>v\notin C</math> (an edge going away from the cycle), then include in <math>E^\prime</math> a new edge <math>e = (v_C, v)</math>, and define <math>w^\prime(e) = w(u,v) </math>.
* If <math>(u,v)</math> is an edge in <math>E</math> with <math>u\notin C</math> and <math>v\notin C</math> (an edge unrelated to the cycle), then include in <math>E^\prime</math> a new edge <math>e = (u, v)</math>, and define <math>w^\prime(e) = w(u,v) </math>.

For each edge in <math>E^\prime</math>, we remember which edge in <math>E</math> it corresponds to.

Now find a minimum spanning arborescence <math>A^\prime</math> of <math>D^\prime</math> using a call to <math>f(D^\prime, r,w^\prime)</math>.
Since <math>A^\prime</math> is a spanning arborescence, each vertex has exactly one incoming edge.
Let <math>(u, v_C)</math> be the unique incoming edge to <math>v_C</math> in <math>A^\prime</math>.
This edge corresponds to an edge <math>(u,v) \in E</math> with <math>v \in C</math>.
Remove the edge <math>(\pi(v),v)</math> from <math>C</math>, breaking the cycle.
Mark each remaining edge in <math>C</math>.
For each edge in <math>A^\prime</math>, mark its corresponding edge in <math>E</math>.
Now we define <math>f(D, r, w)</math> to be the set of marked edges, which form a minimum spanning arborescence.

Observe that <math>f(D, r, w)</math> is defined in terms of <math>f(D^\prime, r, w^\prime)</math>, with <math>D^\prime</math> having strictly fewer vertices than <math>D</math>. Finding <math>f(D, r, w)</math> for a single-vertex graph is trivial (it is just <math>D</math> itself), so the recursive algorithm is guaranteed to terminate.

==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, [[Harold N. Gabow|Gabow]], [[Zvi Galil|Galil]], Spencer, and [[Robert Tarjan|Tarjan]] produced a faster implementation, with running time <math>O(E + V \log V)</math>.

== References ==
{{reflist}}
* {{citation | first1=Yeong-Jin |last1=Chu |first2=Tseng-Hong |last2 = Liu |title= On the Shortest Arborescence of a Directed Graph |journal=Scientia Sinica |volume=XIV |issue=10 |year= 1965| pages=1396–1400 | url =https://github.com/jungyeul/chu-liu-1965/blob/main/chu-liu-1965.pdf}}
* {{citation | first1=J. |last1=Edmonds |title=Optimum Branchings | journal= Journal of Research of the National Bureau of Standards Section B | volume=71B |issue=4 |year= 1967 |pages=233–240 | doi=10.6028/jres.071b.032|doi-access=free }}
* {{citation | first1=R. E.|last1=Tarjan |author1-link=Robert Tarjan|title=Finding Optimum Branchings | journal =Networks | volume=7 |year=1977 | pages=25–35 | doi=10.1002/net.3230070103}}
* {{citation | first1=P.M.|last1= Camerini |first2= L. |last2=Fratta | first3 =F. |last3= Maffioli |title=A note on finding optimum branchings | journal=Networks | volume=9 |issue= 4 |year= 1979| pages=309–312 | doi=10.1002/net.3230090403}}
* {{citation | first1=Alan |last1= Gibbons |title=Algorithmic Graph Theory | publisher=Cambridge University press | year=1985 |isbn= 0-521-28881-9 }}
* {{citation | first1=H. N. |last1=Gabow|author1-link=Harold N. Gabow |first2=Z.|last2=Galil|author2-link=Zvi Galil |first3=T.|last3=Spencer | first4=R. E.|last4=Tarjan |author4-link=Robert Tarjan | title=Efficient algorithms for finding minimum spanning trees in undirected and directed graphs|journal= Combinatorica |volume=6 |issue=2 |year=1986|pages= 109–122 | doi=10.1007/bf02579168|s2cid=35618095}}
* {{citation | first1=V. |last1=Buslov |title=Algorithm for Sequential Construction of Spanning Minimal Directed Forests | journal= Journal of Mathematical Sciences | volume=275 |year= 2023 |pages=117-129 | doi=10.1007/s10958-023-06666-w|doi-access=free }}

== External links ==
*[https://github.com/atofigh/edmonds-alg/ Edmonds's algorithm ( edmonds-alg )] – An 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.
*NetworkX, a [[python (programming language)|python]] library distributed under [[BSD]], has an implementation of [https://networkx.github.io/documentation/networkx-1.10/reference/generated/networkx.algorithms.tree.branchings.Edmonds.html Edmonds' Algorithm].
*[https://pypi.org/project/spanning-forest-builder/ (spanning-forest-builder 0.0.2)] – Library for constructing oriented forests of minimum weight.

{{Graph traversal algorithms}}

[[Category:Graph algorithms]]

Edmonds' algorithm - Revision history

imported>DanilaBudylyov: /* External links */