# Questions tagged [matching]

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

6 questions
Filter by
Sorted by
Tagged with
398 views

### Can a generic ILP solver find graph matchings as fast as a specialized algorithm?

Finding a maximum matching, or a maximum-weight matching, is a well-known problem, which has polynomial-time combinatorial algorithms. It can also be formulated as an integer linear program. In ...
32 views

### Finding an augmenting path or cycle in weighted graph

Suppose we are given a (simple) graph with non-negative edge weights, along with a matching $M$, which may or may not be max weight. I know that $M$ will be max weight if and only if the graph does ...
197 views

### Counting the number of matchings in a complete bipartite graph

I am trying to count the number of matchings in a complete bipartite graph (perfect as well as imperfect). It's relatively easy for me to convince myself that there is $n!$ perfect matchings in the ...
68 views

### Problem classification: optimal weights for Weighted Arithmetic Mean

I want to write an optimisation problem then solve it, to get optimised weights to compute a final score using a weighted arithmetic mean. The problem is as follows. I have an entity (an input vector ...
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 ...