CoreSource checked

Edmonds' Blossom Algorithm

Edmonds' Blossom Algorithm uses shrinking odd cycles so augmenting paths can be found in non-bipartite graphs for general graph matching.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Graph Traversal
Difficulty: Intermediate
Family: Graph Matching
Tier: Core
Status: Verified
Review: Source Checked
Sources: 3
Formulas: 0
Relationships: 7
Code example: Ready
Visualization: Ready

Overview

Edmonds' Blossom Algorithm handles general graph matching by shrinking odd cycles so augmenting paths can be found in non-bipartite graphs.

Core Concepts

general graph matchinggraph matchingaugmenting pathmatchinggraph traversal

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(E)

Average

O(V^2 E)

Worst

O(V^2 E)

Space

O(V + E)

When to Use

Use Edmonds' Blossom Algorithm when solving graph matching and you want to benefit from shrinking odd cycles so augmenting paths can be found in non-bipartite graphs.
Choose it when O(V^2 E) average/worst-case time and O(V + E) memory match your workload profile.
Prefer it over Bipartite Matching DFS or Gale-Shapley Algorithm when the problem structure favors general graph matching.

When Not to Use

Avoid when the graph model does not match the method's direction, weight, or connectivity assumptions.
Avoid when a simpler traversal gives the same information with less bookkeeping.

What It Does

Edmonds' Blossom Algorithm uses shrinking odd cycles so augmenting paths can be found in non-bipartite graphs for general graph matching
Organizes the work around general graph matching and graph matching.

Use Cases

Production and research workloads requiring graph matching via shrinking odd cycles so augmenting paths can be found in non-bipartite graphs.
Graph Matching pipelines where O(V^2 E) time and O(V + E) space fit system constraints.
Engineering comparisons against Bipartite Matching DFS and Gale-Shapley Algorithm when tuning graph matching.

Inputs

Undirected graph G = (V, E) (bipartite or general)

Outputs

Maximum-cardinality set of pairwise non-adjacent edges M ⊆ E

Pseudocode

1.Construct the graph representation G = (V, E) and initialize auxiliary structures for general graph matching (graph matching).
2.Seed the initial frontier, partition, or residual capacities according to Edmonds' Blossom Algorithm's invariants.
3.Iteratively process vertices or edges by shrinking odd cycles so augmenting paths can be found in non-bipartite graphs.
4.Maintain structural invariants (general graph matching, graph matching, augmenting path) and prune or contract resolved subproblems.
5.Extract and return the final graph matching structure from the converged graph state.

Canonical Example

Input: Undirected graph G = (V, E) (bipartite or general) configured for a representative graph matching test case
Output: Maximum-cardinality set of pairwise non-adjacent edges M ⊆ E satisfying Edmonds' Blossom Algorithm invariants
Explanation: Edmonds' Blossom Algorithm processes the input by shrinking odd cycles so augmenting paths can be found in non-bipartite graphs, tracking general graph matching and graph matching to produce the verified graph matching result.

Implementation Notes

Represent vertices and edges explicitly before optimizing storage.
Keep graph direction, weights, and multiedges clear in tests.
Record tie-breaking when multiple valid outputs exist.

Common Pitfalls

Using the method on the wrong graph type, such as directed versus undirected or weighted versus unweighted.
Forgetting disconnected components or isolated vertices.
Letting tie-breaking hide nondeterministic output in tests.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show shrinking odd cycles so augmenting paths can be found in non-bipartite graphs on a small general graph matching example.

Step 1 of 5: Construct the graph representation G = (V, E) and initialize auxiliary structures for general graph matching (graph matching).

graph-traversal-mechanism

Notes

Edmonds' Blossom Algorithm operates in O(V^2 E) time and O(V + E) space within the Graph Matching family. Often compared with Bipartite Matching DFS and Gale-Shapley Algorithm.