Content deleted Content added
m math formatting Tags: Mobile edit Mobile app edit iOS app edit |
Added |
||
| (6 intermediate revisions by 5 users not shown) | |||
Line 19:
| year = 1965
| pages = 449–467
| doi-access = free
}}</ref> Given a general [[Graph (discrete mathematics)|graph]] {{math|1=''G'' = (''V'', ''E'')}}, the algorithm finds a matching {{mvar|M}} such that each vertex in {{mvar|V}} is incident with at most one edge in {{mvar|M}} and {{math|{{abs|''M''}}}} is maximized. The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph. Unlike [[bipartite graph|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 {{math|[[Big O notation|''O'']]({{abs|''E''}}{{abs|''V''}}{{sup|2}})}}, where {{math|{{abs|''E''}}}} is the number of [[edge (graph)|edges]] of the graph and {{math|{{abs|''V''}}}} is its number of [[vertex (graph)|vertices]]. A better running time of <math>O( |E| \sqrt{ |V| } )</math> for the same task can be achieved with the much more complex algorithm of Micali and Vazirani.<ref name = "micali">{{cite conference
Line 199 ⟶ 200:
===Weighted matching===
The matching problem can be generalized by assigning weights to edges in {{mvar|G}} and asking for a set {{mvar|M}} that produces a matching of maximum (minimum) total weight: this is the [[maximum weight matching]] problem. This problem can be solved by a combinatorial algorithm that uses the unweighted Edmonds's algorithm as a subroutine.<ref name = "matching book"/> Vladimir Kolmogorov provides an efficient C++ implementation of this.<ref name = blossom5>{{citation
| author = Kolmogorov, Vladimir
| title = Blossom V: A new implementation of a minimum cost perfect matching algorithm
Line 214 ⟶ 215:
<references/>
[[Category:Graph algorithms]]
[[Category:Matching (graph theory)]]
| |||