Edmonds' algorithm

From Wikipedia, the free encyclopedia
Jump to: navigation, search
This article is about the optimum branching algorithm. For the maximum matching algorithm, see 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, 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 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[edit]

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

Algorithm[edit]

Description[edit]

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

The precise description is as follows. Given a weighted directed graph D with root r 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 v other than the root, mark an (arbitrarily chosen) incoming edge of lowest cost. Denote the other endpoint of this edge by \pi(v). The edge is now denoted as (\pi(v),v) with associated cost w(\pi(v),v). If the marked edges form an SRT (Shortest Route Tree), f(D) 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 C. We now define a weighted directed graph D^\prime having a root r^\prime as follows. The nodes of D^\prime are the nodes of D not in C plus a new node denoted v_C.

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

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

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

We include no other edges in D^\prime.

The root r^\prime of D^\prime is simply the root r in D.

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

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

Implementation[edit]

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.

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 v\rbrace find an edge  e = (x,v) such that w(e) = max{ w(y,v)|(y,v) \in Ei} if w(e) ≤ 0 then goto A } if BE \cup \lbrace e\rbrace contains a circuit { i=i+1 construct G_i by shrinking C_i to u_i modify BE, BV and some edge weights } BE \leftarrow BE \cup {e} goto A

B: while i ≠ 0 { reconstruct G_{i-1} 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^i\rbrace }else{ BE \leftarrow BE \cup \lbrace e|e \in C_i and e \ne \tilde{e}_i\rbrace } i=i-1 } Maximum branching weight = \sum_{e \in BE} w(e)

References[edit]

  • Chu, Y. J.; Liu, T. H. (1965), "On the Shortest Arborescence of a Directed Graph", Science Sinica 14: 1396–1400 
  • Edmonds, J. (1967), "Optimum Branchings", J. Res. Nat. Bur. Standards 71B: 233–240 
  • Tarjan, R. E. (1977), "Finding Optimum Branchings", Networks 7: 25–35 
  • Camerini, P.M.; Fratta, L.; Maffioli, F. (1979), "A note on finding optimum branchings", Networks 9: 309–312 
  • Gibbons, Alan (1985), Algorithmic Graph Theory, Cambridge University press, ISBN 0-521-28881-9 
  • Gabow, H. N.; Galil, Z.; Spencer, T.; Tarjan, R. E. (1986), "Efficient algorithms for finding minimum spanning trees in undirected and directed graphs", Combinatorica 6: 109–122 

External links[edit]