Questions tagged [matching]
A matching is a subset of the edges of a graph, such that no edge in the subset shares a vertex with another.
7
questions
10
votes
1
answer
5k
views
Monotone bijections between lists of intervals
I have the following problem:
Input: two sets of intervals $S$ and $T$ (all endpoints are integers).
Query: is there a monotone bijection $f:S \to T$?
The bijection is monotone w.r.t. the set ...
8
votes
2
answers
598
views
Min weight perfect matching with even number of red edges
Consider a weighted graph with some red edges.
We are interested in finding a perfect matching, such that the number of red edges is even, and under the previous constraints, the weight is minimized.
...
5
votes
1
answer
2k
views
Assignment problem with multiple workers for each job
I am wondering if there are any results on the following version of the assignment problem. We are given a set of jobs $J$ and a set of workers $W$, and for each job $j$ and worker $w$ we are given ...
4
votes
1
answer
375
views
Is Permanent $+$-reducible?
Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$.
Is ...
4
votes
2
answers
257
views
Complexity of Uniform Generation of Perfect Matchings
Jerrum,Valiant and Vazirani on their paper "Random generation of combinatorial structures from a uniform" (http://www.cc.gatech.edu/~vazirani/AppCount.pdf) talk about seeing problems related to ...
2
votes
2
answers
6k
views
Reducing a minimum cost edge-cover problem to minimum cost weighted bipartie perfect matching
I have a set of edges [m,n] of a bipartie graph U, V with a cost assigned to each edge and I need to find the minimum cost edge-cover covering all nodes in U, V. There is one additional constraint is ...
1
vote
0
answers
164
views
Is the matching polytope integral?
In this document https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture9.pdf
they prove the integrality of the matching polytope using the integrality of the perfect matching polytope.
The ...