Questions tagged [matching-theory]
For questions about matchings in graph theory. A matching on a graph is a set of edges such that no two edges share a common vertex.
11 questions from the last 365 days
1
vote
0
answers
149
views
Inequalities in the classic proof of perfect matching in Erdős–Rényi graph
I am checking the classic paper by Erdős and Rényi, "On the existence of a factor of degree one of a connected random graph" with the link here. I am curious about the computation of the ...
- 97
0
votes
0
answers
42
views
How to determine if two matchings are related by a permutation?
Let $n \geq 2$ be an integer. Let
\begin{align*}
V &= \{(i, j); 1 \leq i, j \leq n \text{ and } i \neq j \} \\
E &= \{ \{v_1, v_2\}; v_1, v_2 \in V \text{ and } v_1 \neq v_2 \}.
\end{align*}
...
- 5,215
0
votes
1
answer
77
views
Bipartite matching where every adjacent pair of vertex on the left side of the graph has at least 1 vertex matched
The question is as stated above. I want to devise bipartite matching algorithm where it determies whether every adjacent pair of vertex on the left side of the bipartite graph has at least 1 vertex ...
1
vote
0
answers
48
views
How to solve a optimal matching problem where the "quality" of matching is only determined once all nodes are matched
Note: I'm not a mathematician; I'm just a biologist with basic math background trying to solve a scientific problem, so please excuse my ignorance.
The gist of the problem is as follows:
I have two ...
4
votes
0
answers
113
views
Find necessary & sufficient conditions for two families of sets to have $m$ pairwise disjoint common partial transversals of given sizes
Let $S$ be a finite set, $I$ a finite index set, $\mathcal A=(A_i:i\in I)$ and $\mathcal B=(B_i:i\in I)$ families of subsets of $S$.
For $J\subseteq I$, let $A(J)$ denote $\bigcup_{j\in J} A_j$.
A ...
- 1,644
1
vote
0
answers
32
views
Any updates on "The minimum cost perfect matching problem with conflict pair constraints"?
The subject of the paywalled article The minimum cost perfect matching problem with conflict pair constraints (MCPMPC) are perfect matchings of minimum cost that do not contain certain pairs of edges; ...
- 13.2k
1
vote
1
answer
126
views
Finding a max weight matching of specified size in general graphs
I am looking for an algorithm that can compute a maximum weight matching among all matchings with at least $k$ edges for some integer $k$. Note that this matching may have smaller weight than an ...
- 11
3
votes
1
answer
140
views
Generalizations of a theorem of Edmonds/Tutte on existence of a perfect matching in a graphs
It is well known that for a bipartite graph $G$ with bi-adjacency matrix $A$, then $\det A \neq 0$ (as a polynomial) iff $G$ has a perfect matching (there is a similar result for general graphs with ...
- 129
1
vote
1
answer
54
views
Complexity of maximum weight-sum matching for cycle graphs
I need to determine a matching with maximal weight-sum for a cycle graph with positive, negative and zero edge-weights.
Question:
What is the fastest way of calculating such a matching?
Because of ...
- 13.2k
2
votes
1
answer
315
views
Bipartite matching with a pairwise constraint
A long time ago I remember seeing a very clever construction for the following problem, but I can't find a reference for it anywhere: suppose I have a bipartite graph $G=(U\cup V, E)$, and the ...
- 4,049
4
votes
0
answers
118
views
Reorganizational matching
Motivation. My friend works in an organization that is re-organizing itself in the following somewhat laborious way: There are $n$ people currently sitting on $n$ jobs in total (everyone has one job). ...
- 48.8k