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.

Filter by
Sorted by
Tagged with
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 ...
a3nm's user avatar
  • 9,259
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. ...
Chao Xu's user avatar
  • 4,399
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 ...
George Octavian Rabanca's user avatar
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 ...
Turbo's user avatar
  • 12.8k
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 ...
ricardorr's user avatar
  • 541
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 ...
Sadache's user avatar
  • 129
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 ...
Karagounis Z's user avatar