Blossom algorithm (original) (raw)
In graph theory, the blossom algorithm is an algorithm for constructing maximum matchings on graphs. The algorithm was developed by Jack Edmonds in 1961, and published in 1965. 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.
| Property | Value | |||
|---|---|---|---|---|
| dbo:abstract | In graph theory, the blossom algorithm is an algorithm for constructing maximum matchings on graphs. The algorithm was developed by Jack Edmonds in 1961, and published in 1965. 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 | |
| dbo:thumbnail | wiki-commons:Special:FilePath/Edmonds_augmenting_path.svg?width=300 | |||
| dbo:wikiPageID | 24277294 (xsd:integer) | |||
| dbo:wikiPageLength | 16965 (xsd:nonNegativeInteger) | |||
| dbo:wikiPageRevisionID | 1111919935 (xsd:integer) | |||
| dbo:wikiPageWikiLink | dbr:Total_unimodularity dbr:Berge's_lemma dbr:Algorithm dbc:Matching_(graph_theory) dbr:Alexander_Schrijver dbr:Graph_(discrete_mathematics) dbr:Maximum_weight_matching dbc:Graph_algorithms dbr:Linear_programming dbr:Edge_(graph) dbr:Ford–Fulkerson_algorithm dbr:Graph_theory dbr:Jack_Edmonds dbr:Big_O_notation dbr:Bipartite_graph dbr:Edge_contraction dbr:Polyhedral_combinatorics dbr:Maximum_matching dbr:If_and_only_if dbr:Blossom_(graph_theory) dbr:Forest_(graph_theory) dbr:Polytope dbr:Vertex_(graph) dbr:File:Blossom_contraction.png dbr:File:Edmonds_augmenting_path.svg dbr:File:Edmonds_blossom.svg dbr:File:Edmonds_lifting_end_point.svg dbr:File:Edmonds_lifting_path.svg dbr:File:Forest_expansion.png dbr:File:Path_detection.png dbr:File:Path_lifting.png | |||
| dbp:wikiPageUsesTemplate | dbt:Code dbt:Math dbt:Mvar dbt:Short_description dbt:Sub dbt:Sup dbt:Abs | |||
| dcterms:subject | dbc:Matching_(graph_theory) dbc:Graph_algorithms | |||
| gold:hypernym | dbr:Algorithm | |||
| rdf:type | dbo:Software yago:WikicatLakes yago:BodyOfWater109225146 yago:Lake109328904 yago:PhysicalEntity100001930 yago:YagoGeoEntity yago:YagoPermanentlyLocatedEntity yago:River109411430 yago:Stream109448361 yago:Thing100002452 yago:WikicatRivers | |||
| rdfs:comment | In graph theory, the blossom algorithm is an algorithm for constructing maximum matchings on graphs. The algorithm was developed by Jack Edmonds in 1961, and published in 1965. 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. (en) El Algoritmo del Blossom o Algoritmo de Emparejamiento de Edmonds es un algoritmo de teoría de grafos para construir emparejamientos máximos en grafos. El algoritmo fue desarrollado por Jack Edmonds en 1961, y publicado en 1965. El emparejamiento máximo es construido iterativamente mejorando el emparejamiento actual a través de caminos m-incrementos mientras al menos exista uno. La idea esencial del algoritmo es que un ciclo de longitud impar (blossom) es contraído en un solo vértice para luego continuar la búsqueda de caminos m-incrementos en el grafo resultante. La idea de contraer los ciclos de longitud impar se debe a que si no se hiciera el mismo algoritmo de búsqueda de caminos m-incrementos al entrar en uno de estos ciclos y salir pudiera reportar falsos positivos. (es) En informatique, plus précisément en théorie des graphes, l'algorithme d'Edmonds pour les couplages (blossom algorithm en anglais), aussi connu sous le nom d'algorithme des fleurs et des pétales est un algorithme pour construire des couplages maximaux sur les graphes. L'algorithme a été développé par Jack Edmonds en 1961, et publié en 1965. Étant donné un graphe quelconque G = (V, E), l'algorithme trouve un couplage M tel que chaque sommet de V est incident à au plus une arête dans E et M est de cardinal maximal. Le couplage est construit en améliorant itérativement un couplage vide initial le long de chemins augmentant dans le graphe. Contrairement au couplage biparti, ce couplage se base sur l'idée qu'un cycle de longueur impaire dans le graphe (fleur) est contracté en un seul sommet, la (fr) Алгоритм сжатия цветков (англ. Blossom algorithm) — алгоритм в теории графов для построения наибольших паросочетаний на графах. Алгоритм разработал Джек Эдмондс в 1961 году и опубликовал в 1965 году. Если дан граф G=(V, E) общего вида, алгоритм находит паросочетание M такое, что каждая вершина из V инцидентна не более чем одному ребру из M и | M | максимально. Паросочетание строится путём итеративного улучшения начального пустого паросочетания вдоль увеличивающих путей графа. В отличие от двудольного паросочетания ключевой новой идеей было сжатие нечётного цикла в графе (цветка) в одну вершину с продолжением поиска итеративно по сжатому графу. (ru) |
| rdfs:label | Blossom algorithm (en) Algoritmo de Emparejamiento de Edmonds (es) Algorithme d'Edmonds pour les couplages (fr) Алгоритм сжатия цветков (ru) | |||
| owl:sameAs | freebase:Blossom algorithm yago-res:Blossom algorithm wikidata:Blossom algorithm dbpedia-es:Blossom algorithm dbpedia-fa:Blossom algorithm dbpedia-fr:Blossom algorithm dbpedia-ru:Blossom algorithm dbpedia-sr:Blossom algorithm dbpedia-vi:Blossom algorithm https://global.dbpedia.org/id/7QKK | |||
| prov:wasDerivedFrom | wikipedia-en:Blossom_algorithm?oldid=1111919935&ns=0 | |||
| foaf:depiction | wiki-commons:Special:FilePath/Blossom_contraction.png wiki-commons:Special:FilePath/Edmonds_augmenting_path.svg wiki-commons:Special:FilePath/Edmonds_blossom.svg wiki-commons:Special:FilePath/Edmonds_lifting_end_point.svg wiki-commons:Special:FilePath/Edmonds_lifting_path.svg wiki-commons:Special:FilePath/Forest_expansion.png wiki-commons:Special:FilePath/Path_detection.png wiki-commons:Special:FilePath/Path_lifting.png | |||
| foaf:isPrimaryTopicOf | wikipedia-en:Blossom_algorithm | |||
| is dbo:knownFor of | dbr:Jack_Edmonds | |||
| is dbo:wikiPageRedirects of | dbr:Edmonds's_matching_algorithm | |||
| is dbo:wikiPageWikiLink of | dbr:University_of_Waterloo dbr:Dulmage–Mendelsohn_decomposition dbr:Integral_polytope dbr:Maximum_cardinality_matching dbr:Claw-free_graph dbr:Gallai–Edmonds_decomposition dbr:Jack_Edmonds dbr:Edmonds's_matching_algorithm | |||
| is foaf:primaryTopic of | wikipedia-en:Blossom_algorithm |
