Edmonds' algorithm

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

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== ===Description=== The algorithm takes as input a directed graph D = \langle V, E \rangle where V is the set of nodes and E is the set of directed edges, a distinguished vertex r \in V called the root, and a real-valued weight w(e) for each edge e \in E . It returns a spanning arborescence A rooted at r of minimum weight, where the weight of an arborescence is defined to be the sum of its edge weights, w(A) = \sum_{e \in A}{w(e)} . The algorithm has a recursive description. Let f(D, r, w) denote the function which returns a spanning arborescence rooted at r of minimum weight. We first remove any edge from E whose destination is r . 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 v other than the root, find the edge incoming to v of lowest weight (with ties broken arbitrarily). Denote the source of this edge by \pi(v) . If the set of edges P = \{(\pi(v),v) \mid v \in V \setminus \{ r \} \} does not contain any cycles, then f(D,r,w) = P . Otherwise, P contains at least one cycle. Arbitrarily choose one of these cycles and call it C . We now define a new weighted directed graph D^\prime = \langle V^\prime, E^\prime \rangle in which the cycle C is "contracted" into one node as follows: The nodes of V^\prime are the nodes of V not in C plus a new node denoted v_C . If (u,v) is an edge in E with u\notin C and v\in C (an edge coming into the cycle), then include in E^\prime a new edge e = (u, v_C) , and define w^\prime(e) = w(u,v) - w(\pi(v),v) . If (u,v) is an edge in E with u\in C and v\notin C (an edge going away from the cycle), then include in E^\prime a new edge e = (v_C, v) , and define w^\prime(e) = w(u,v) . If (u,v) is an edge in E with u\notin C and v\notin C (an edge unrelated to the cycle), then include in E^\prime a new edge e = (u, v) , and define w^\prime(e) = w(u,v) . For each edge in E^\prime , we remember which edge in E it corresponds to. Now find a minimum spanning arborescence A^\prime of D^\prime using a call to f(D^\prime, r,w^\prime) . Since A^\prime is a spanning arborescence, each vertex has exactly one incoming edge. Let (u, v_C) be the unique incoming edge to v_C in A^\prime . This edge corresponds to an edge (u,v) \in E with v \in C . Remove the edge (\pi(v),v) from C , breaking the cycle. Mark each remaining edge in C . For each edge in A^\prime , mark its corresponding edge in E . Now we define f(D, r, w) to be the set of marked edges, which form a minimum spanning arborescence. Observe that f(D, r, w) is defined in terms of f(D^\prime, r, w^\prime) , with D^\prime having strictly fewer vertices than D . Finding f(D, r, w) for a single-vertex graph is trivial (it is just D itself), so the recursive algorithm is guaranteed to terminate. ==Running time== The running time of this algorithm is O(EV) . A faster implementation of the algorithm due to Robert Tarjan runs in time O(E \log V) for sparse graphs and O(V^2) 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 O(E + V \log V) .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1271330582 under CC BY-SA 4.0; modifications have been made.