# Maximum matching algorithms in igraph

Registered by Tamás Nepusz on 2011-06-06

Implementation plans for maximum matching algorithms (bipartite and general, weighted and unweighted) in igraph

## Blueprint information

Status:
Not started
Approver:
Priority:
Medium
Drafter:
Direction:
Approved
Assignee:
Definition:
Drafting
Series goal:
None
Implementation:
Unknown
Milestone target:
None

### Whiteboard

Maximum unweighted matching in bipartite graphs: Hopcroft-Karp algorithm (O(|E| * sqrt(|V|) worst case), or push-relabel. Python implementation of the Hopcroft-Karp algorithm: [3]. Some papers suggest that push-relabel is better [4,5]

Maximum unweighted/weighted matching in general graphs: Edmonds' matching algorithm (O(|V|^4)) or the Micali-Vazirani algorithm (O(|E| * sqrt(|V|)) [1]. Kolmogorov's implementation [2].

[1] Micali, Silvio; Vazirani, Vijay (1980), "An O(V1/2E) algorithm for finding maximum matching in general graphs", 21st Annual Symposium on Foundations of Computer Science, (IEEE Computer Society Press, New York): 17–27

[2] Kolmogorov, Vladimir (2009), "Blossom V: A new implementation of a minimum cost perfect matching algorithm", Mathematical Programming Computation 1 (1): 43–67

Proposed interface in the C layer:

int igraph_maximum_bipartite_matching(const igraph_t* graph, const igraph_vector_bool_t* types, igraph_integer_t* matching_size, igraph_vector_t* matching, const igraph_vector_t* weights);
int igraph_maximum_matching(const igraph_t* graph, igraph_integer_t* matching_size, igraph_vector_t* matching, const igraph_vector_t* weights);

(?)

### Work Items

This blueprint contains Public information
Everyone can see this information.

No subscribers.