Questions tagged [matching-theory]
For questions about matchings in graphs.
566
questions
0
votes
3
answers
63
views
An Interesting Optimization Problem With Permutation Function [closed]
Define a permutation mapping $\sigma(\cdot):\mathcal{V}\longmapsto\mathcal{V}$ with $\mathcal{V}=\{1,2,\dots,N\}$, which can transform a permutation consisting of $1,2,\dots,N$ into another ...
- 11
-1
votes
0
answers
10
views
Maximum multiple matching with maximum cost with constraint [closed]
There are n people and m projects.Each people can do multiple projects. It has cost assigned to do each project by that person . We have to maximize the cost and find the maximum matching from person ...
0
votes
0
answers
34
views
How DTW decides which element to take next?
I'm currently working on an DTW algorithm implementation and do have a question about how DTW works if the next steps are the same or if the correct next step is the actually not less-cost one.
I do ...
0
votes
1
answer
48
views
A proof for the statement: The 3-Dimensional matching problem is NP-Complete
The 3-Dimensional Matching Problem is relatively well known in the fields of discrete mathematics and computer science. The problem consists of determining whether a tripartite
$3$-hypergraph with ...
- 3,408
0
votes
0
answers
8
views
Bipartite Matching With Distant Constraints
I am investigating the complexity of the following problem.
Let a complete bipartite graph $G = (V \cup V', E: V \times V')$ with |V| < |V'|, where the nodes have weights $w: V \cup V' \to \mathbb{...
- 19
2
votes
1
answer
41
views
If a graph is 1-factoreable, then it has no cut vertex.
I'm trying to prove the statement: if a graph $G$ is 1-factorable, then $G$ has no cut vertex.
Assuming $G$ has a cut vertex, let be $v\in V(G)$ a cut vertex of $G$. Then the connected components of $...
- 2,107
2
votes
0
answers
16
views
Matching number of a graph is equal to the independence number of its line graph.
Let $\alpha'(G)$ the matching number of a graph $G$, $L(G)$ its line graph and $\alpha(L(G))$ the stability number of its line graph. I need to prove that $\alpha'(G)=\alpha(L(G))$. Let $M$ be a ...
- 2,107
1
vote
0
answers
18
views
How sensitive are maximum-size matchings to edge deletion in random graphs?
My question concerns the sensitivity of maximum-size matchings (and more generally maximum-size $k$-cycle collections) to deletion of an edge in the graph.
Given a graph $G$, let a $k$-cycle be a ...
- 11
0
votes
1
answer
32
views
Understanding proof of Hall's graph theorem
I am struggling with understanding proof of Halls theorem.
Theorem: Let $G=(V_1\cup V_2,E)$ be a bipartite graph and for each $U\subseteq V_1$ let $$N_{G}(U)=\{v\in V_2\ :\ \exists u\in U\text{ such ...
- 115
1
vote
1
answer
39
views
Problem in proving that every tree has at most one perfect matching.
I would like to prove that every tree has at most one perfect matching. I approached it in the same way as described here: Perfect matching in a tree. However, I don't understand the concluding ...
user1316790
1
vote
1
answer
43
views
A matching problem with $N$ men, $N$ women and $N$ houses [closed]
Consider a matching problem with $N$ men, $N$ women and $N$ houses where each man has to be paired with exactly $1$ woman and then each couple has to be allotted to $1$ house. Now let's consider all $...
- 113
1
vote
0
answers
32
views
Parity of number of crossings of chord diagram
I would like to define the following sign for a given perfect matching $P$ of set of $2n$ elements:
$$\sigma_P=(-1)^k$$
where $k$ is the number of crossings in the chord diagram associated to $P$.
Is ...
0
votes
1
answer
39
views
Perfect matching on bipartite graph with $n(n-1)$ number of edges
Suppose $G$ is a $(X,Y)$ graph with $|X| = |Y| = n \geq 1$. Prove that if $|A(G)| > n(n-1)$ then $G$ has a perfect matching.
I'm looking for a hint on showing that $|N(S)| \geq |S|, \forall S \...
- 367
0
votes
0
answers
37
views
Equivalent statement to Hall's theorem [duplicate]
I am trying to prove that a bipartite graph $G$ on $(X, Y)$, contains a matching perfect to $X$ if and only if
$$
|X\setminus N(T)| \leq |Y\setminus T| \; \; \forall \; T \subseteq Y
$$
Forward ...
- 511
3
votes
1
answer
88
views
Why would solving #MATCHING(bipartite) problem efficiently solve #MATCHING efficiently?
Im gathering information about the matching counting problem for a graph $G$ (#MATCHING($G$)). I found that for the specific case of $G$ being a bipartite graph then the problem has a simple (not ...
- 541