Questions tagged [matching]

For questions on matchings, i.e. sets of disjoint edges of an undirected graph.

Filter by
Sorted by
Tagged with
21
votes
1answer
275 views

Polynomially solvable problems with exponential extension complexity

The maximum matching problem is solvable in polynomial time using Edmonds' blossom algorithm. However, unlike for example the spanning tree polytope, it has been proven fairly recently that the ...
10
votes
1answer
93 views

Relationship between the Assignment Problem and the Stable Marriage Problem

Suppose I'm solving a minimum-weight matching problem in a bipartite graph with sets $\mathcal{I}$ and $\mathcal{J}$, where $w_{ij}$ denotes the weight of matching item $i$ to $j$. I can model the ...