# Questions tagged [matching-theory]

For questions about matchings in graphs.

565 questions
Filter by
Sorted by
Tagged with
67 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 ...
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 ...
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,432
8 views

• 2,107
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
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 ...
32 views

42 views

### Determining whether a housing allocation is in the Core

I have recently been thinking about the housing allocation problem where we have a set of players and a set of houses where players have strict preferences over the houses. I am aware of the Top ...
• 21
25 views

### Finding Nash equilibrium in a basic matching market

I've been working on simulating a market with small numbers of mutually-exclusive sellers and buyers, where each individual can only ever enter one transaction. In pursuing this, I've been trying to ...
45 views

### Generate a schedule for doubles with rotating partners

So I want to set up a schedule of double matches: player A and B vs player C and D. I have a few constraints for setting it up: Each player plays exactly 4 times The scheme should be as fair as ...
• 580
179 views

51 views

• 873
115 views

### Prove that symmetric difference of two perfect matchings is union of disjoint even cycles

Problem: Let $M$ and $N$ be perfect matchings of a finite graph $G$. Prove that their symmetric difference is a union of disjoint even cycles. My attempt: Firstly, if $M = N$, we are done. Now, let us ...
• 1,238
20 views

### Algorithm for k sized matching in a complet weighted graph

as the Title suggest im looking for an algorithm for k sized matching in a weighted complet graph. Any further literature is welcome.
I am working my way through "Matching Theory" by Lovasz and Plummer. Lemma 3.3.13 is where I am stuck. Let $G$ be a graph such that $C(G)=\emptyset$ and let $X$ and $Y$ be barriers such that ...