Edmonds's algorithm

In graph theory, a branch of mathematics, Edmonds's algorithm or Chu–Liu/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 independently first by Chu and 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.

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.

Execution

$BV leftarrow BE leftarrow varnothing$ i=0 A: if $BV = V_i$ then goto B for some vertex $v otin BV$ and $v in V_i$ { $BV leftarrow BV cup lbrace v brace$ find an edge $e = (x,v)$ such that w(e) = max{ w(w,y)|(w,y) $in$ E_i} if w(e) ≤ 0 then goto A } if $BE cup lbrace e brace$ contains a circuit { i=i+1 construct $G_i$ by shrinking $C_i$ to $u_i$ modify BE, BV and some edge weights } $BV 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 e e_0^i brace$ }else{ $BE leftarrow BE cup lbrace e|e in C_i$ and $e e ilde{e}_i brace$ } i=i-1 } Maximum branching weight = $sum_{e in BE} w(e)$

To author: modify BE, BV and some edge weights - how?
$u_i$ - what is $u_i$ ?

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.
* Alan Gibbons "Algorithmic Graph Theory," Cambridge University press, 1985 ISBN: 0-521-28881-9

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

* [http://algowiki.net/wiki/index.php/Edmonds%27s_algorithm AlgoWiki - Edmonds's algorithm] - A public-domain implementation of Edmonds's algorithm written in Java.

Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

Edmonds-Karp algorithm — In computer science and graph theory, the Edmonds Karp algorithm is an implementation of the Ford Fulkerson method for computing the maximum flow in a flow network in mathcal{O}(|V| cdot |E|^2). It is asymptotically slower than the relabel to… … Wikipedia
Jack Edmonds — Jack R. Edmonds is a mathematician, regarded as one of the most important contributors to the field of combinatorial optimization. He was the recipient of the 1985 John von Neumann Theory Prize.From 1969 on, with the exception of 1991 1993, he… … Wikipedia
Ford-Fulkerson algorithm — The Ford Fulkerson algorithm (named for L. R. Ford, Jr. and D. R. Fulkerson) computes the maximum flow in a flow network. It was published in 1956. The name Ford Fulkerson is often also used for the Edmonds Karp algorithm, which is a… … Wikipedia
Dinic's algorithm — is a strongly polynomial algorithm for computing the maximum flow in a flow network, conceived in 1970 by Israeli (formerly Soviet) computer scientist Yefim Dinitz. The algorithm runs in O(V2E) time and is similar to the Edmonds–Karp algorithm,… … Wikipedia
Push-relabel maximum flow algorithm — The push relabel algorithm is one of the most efficient algorithms to compute a maximum flow. The general algorithm has O(V^2 E) time complexity, while the implementation with FIFO vertex selection rule has O(V^3) running time, the highest active … Wikipedia
Hopcroft–Karp algorithm — The Hopcroft–Karp algorithm finds maximum cardinality matchings in bipartite graphs in O(sqrt{V} E) time, where V is the number of vertices and E is the number of edges of the graph. [John E. Hopcroft, Richard M. Karp: An n^{5/2} Algorithm for… … Wikipedia
Criss-cross algorithm — This article is about an algorithm for mathematical optimization. For the naming of chemicals, see crisscross method. The criss cross algorithm visits all 8 corners of the Klee–Minty cube in the worst case. It visits 3 additional… … Wikipedia
Levenberg–Marquardt algorithm — In mathematics and computing, the Levenberg–Marquardt algorithm (LMA)[1] provides a numerical solution to the problem of minimizing a function, generally nonlinear, over a space of parameters of the function. These minimization problems arise… … Wikipedia
Gauss–Newton algorithm — The Gauss–Newton algorithm is a method used to solve non linear least squares problems. It can be seen as a modification of Newton s method for finding a minimum of a function. Unlike Newton s method, the Gauss–Newton algorithm can only be used… … Wikipedia
Super-recursive algorithm — In computer science and computability theory, super recursive algorithms are algorithms that are more powerful, that is, compute more, than Turing machines. The term was introduced by Mark Burgin, whose book Super recursive algorithms develops… … Wikipedia

Academic Dictionaries and Encyclopedias

Edmonds's algorithm

Look at other dictionaries:

Share the article and excerpts

Academic Dictionaries and Encyclopedias

Wikipedia

Edmonds's algorithm

Look at other dictionaries:

Share the article and excerpts

Direct link