✳flâneur — a map of the web's best reading

Blossom algorithm - Wikipedia

en.wikipedia.org · 2,999 words · saved by 1 readers

In graph theory, the blossom algorithm is an algorithm for constructing maximum matchings on graphs. The algorithm was developed by Jack Edmonds in 1961,[1] and published in 1965.[2] Given a general graph G = (V, E), the algorithm finds a matching M such that each vertex in V is incident with at most one edge in M and |M| is maximized. The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph. Unlike bipartite matching, the key new idea is that an odd-length cycle in the graph (blossom) is contracted to a single vertex, with the search continuing iteratively in the contracted graph. The algorithm runs in time O(|E||V|2), where |E| is the number of edges of the graph and |V| is its number of vertices. A better running time of 𝑂 ( | 𝐸 | | 𝑉 | ) for the same task can be achieved with the much more complex algorithm of Micali and Vazirani.[3] A major reason that the blossom algorithm is important is that it gave the first proof

Blossom algorithm - Wikipedia Jump to content From Wikipedia, the free encyclopedia Algorithm for finding max graph matchings In graph theory , the blossom algorithm is an algorithm for constructing maximum matchings on graphs . The algorithm was developed by Jack Edmonds in 1961, [ 1 ] and published in 1965. [ 2 ] Given a general graph G = ( V , E ) , the algorithm finds a matching M such that each vertex in V is incident with at most one edge in M and | M | is maximized. The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph. Unlike

Explore this link on the map →

related reading