Blossom algorithm: Difference between revisions

Revision as of 19:22, 13 June 2016

Revision as of 17:29, 6 July 2016

Line 6:

| title = History of Mathematical Programming --- A Collection of Personal Reminiscences

| editor = J.K. Lenstra |editor2=A.H.G. Rinnooy Kan |editor3=A. Schrijver

| pages = 32-5432–54

| publisher = CWI, Amsterdam and North-Holland, Amsterdam

}}</ref> and published in 1965.<ref name = "algorithm">

Line 44:

| year = 1986

| isbn = 963-05-4168-8

}}</ref><ref name = "karp notes">{{citecitation

| author = Karp, Richard

| contribution = Edmonds's Non-Bipartite Matching Algorithm

Line 72:

[[File:Edmonds blossom.svg|500px|alt=Example of a blossom]]

It can be shown<ref name = "tarjan notes">{{citecitation

| author = Tarjan, Robert

| contribution = Sketchy Notes on Edmonds' Incredible Shrinking Blossom Algorithm for General Matching

Line 140:

[[File:forest expansion.png|400px|alt=Forest expansion on line B10]]

Next, it detects a blossom and contracts the graph (lines B20 &ndash; B21).

[[File:blossom contraction.png|400px|alt=Blossom contraction on line B21]]

Line 152:

===Analysis===

The forest ''F'' constructed by the ''find_augmenting_path()'' function is an alternating forest.<ref name = "kenyon report">{{citecitation

| author1 = Kenyon, Claire

| author2 = Lovász, László

Line 183:

===Weighted matching===

The matching problem can be generalized by assigning weights to edges in ''G'' and asking for a set ''M'' that produces a matching of maximum (minimum) total weight. The weighted matching problem can be solved by a combinatorial algorithm that uses the unweighted Edmonds's algorithm as a subroutine.<ref name = "matching book"/> Kolmogorov provides an efficient C++ implementation of this.<ref name = blossom5>{{citecitation

| author = Kolmogorov, Vladimir

| title = Blossom V: A new implementation of a minimum cost perfect matching algorithm