# Questions tagged [matching]

A matching (aka **Independent Edge Set**) in a simple graph is the set of pairwise non-adjacent edges i.e. no two edges have common vertex.

239 questions
Filter by
Sorted by
Tagged with
34 views

### Champions League 36 team algorithm

Does anybody know exactly how the algorithm works that made the new draw for Champions League? Wikipedia says: The 36 teams were manually drawn and then automated software digitally drew their eight ...
• 257
33 views

### Stable roommate problem (Stability in Seating Arrangements)

The Seating Arrangement Problem (SOP) is a specific variant of the Stable Roommates Problem (SRP) that I have defined. In the SRP, pairs of individuals are seated at two-person tables, whereas in the ...
13 views

### What properties of a relation are necessary in a ranking system?

This question is partially about the methodology / process of formulating a question, prior to seeking an answer. Let’s say the minimum we know at the outset is that a group of people can rank each ...
50 views

### Convert a Graph to a Good Graph using Maximum Matching in Bipartite Graphs Algorithm

Consider a graph $G = (V, E)$ where a vertex $v \in V$ is designated as the center if it is connected to every other vertex $u \in V$, such that both $uv$ and $vu$ are present in $E$. A ...
1 vote
37 views

### Finding a matching with a specific weight

Polynomial-time algorithms for finding a maximum-weight matching in a weighted graph are well-known. Suppose I want not the maximum-weight matching, but a matching with a specific weight given as an ...
• 6,152
18 views

### What algorithm should be used to find the closest set of dates?

I have tried to outline my problem as structured as possible, here is a rough overview, I am trying to find the best matching stay for a hotel booking system. If someone inputs check in and checkout ...
33 views

### Optimizing Pairings Between Integers and Intervals for Maximal Matching

Consider the scenario where we are given a collection of n integers. These integers are unordered and may include duplicates. Additionally, we have a set of m ranges, each defined by two integers ...
1 vote
24 views

### Algorithm to find most likely continuation of image over border from set of possible next images

Is there an algorithm that would fit in the following situation: I have a sub image A of a larger image, and a set of sub images B that could (but not necessarily) share border with A. Now the ...
• 111
1 vote
87 views

### A problem maybe related to pattern-matching

Let $\Sigma_{1}=\{a,b\}$ and $\Sigma_{2}=\{t,f\}$. Define the function $f_{w}:\Sigma_{1}^{*}\rightarrow\Sigma_{2}^{*}$ for every $w\in\Sigma_{1}^{*}$; $f_{w}(w')\in\Sigma_{2}^{*}$ is the word obtained ...
• 11
33 views

### How does additional assumptions increase approximation factor?

I am studying the greedy algorithm for maximal weighted matching in arbitrary graphs. I have proven that this algorithm has approximation factor $\frac{1}{2}$. Assume now that the weights in the graph ...
• 123
63 views

### Weighted bipartite maximum cost with a fixed number of vertices

Having a complete bipartite graph with parts $A$ and $B$, which is edge-weighted, is there a way to compute a subgraph with the maximum sum of all weights and: Only a constant number $n$ of vertices ...
• 21
1 vote
24 views

### Stable Flow Problem with one sided preferences

I'm currently working on a problem to come up with ideas to solve a stable flow problem but unlike the traditional stable flow problem where every node has preferences on its incoming and outgoing ...
• 11
60 views

### Max-min one-to-two matching

There are some $n$ people and $2 n$ items. Each person assigns a positive value to each item. The items should be allocated to the people, giving exactly 2 items to each person. The value of a person ...
• 6,152
1 vote
495 views

### Finding all stable matchings in stable marriage problem

I need to find an algorithm for a modified version of the stable marriage problem. In particular, I need to find all possible stable matchings and not only one (unlike what the Gale-Shapley algorithm ...
• 11
17 views

### Finding all stable matchings in stable marriage problem [duplicate]

I need to find an algorithm for a modified version of the stable marriage problem. In particular, I need to find all possible stable matchings and not only one (unlike what the Gale-Shapley algorithm ...
• 11
1 vote
32 views

### Find an assignment discarding a subset of possible assignments

We have a $N \times N$ cost matrix where the cost denotes the amount incurred for assigning a worker to a task. The number of possible assignments is $N!$. Let us call this set of all possible ...
• 11
71 views

### Number of matchings in a bipartite graph having missing edges

Suppose we have a bipartite graph with $N$ vertices on either side. In the full bipartite graph, the number of edges is $N^2$ and the number of possible matchings (i.e. assignments) is $N!$. Now ...
• 11
1 vote
125 views

### High-multiplicity maximum-weight matching

There are $n$ people and $m$ jobs. We would like to assign at most one job to each person. For each person,job pair, there is a positive value determining the fitness of this person to that job. The ...
• 6,152
79 views

### Distribution of $k$-matchings in a random graph

Take the Erdos-Renyi random graph $G(n,p)$, i.e. the random graph with $n$ vertices and where each possible edge has an independent probability of $p$ of being present. Recall that a $k$-matching is a ...
381 views

### Partitioning a graph into connected pairs and triplets

We need to partition an undirected graph into connected subgraphs of size between $2$ and $k$, where $k$ is an integer. When $k=2$, the problem is equivalent to the perfect matching problem which is ...
• 81
1 vote
79 views

### Reducing the min weight perfect matching problem to a T-join

My lecture notes for $T$-joins states: If $T = V$ then $T$ -joins of cardinality $V/2$ are exactly the perfect matchings of $G$ = $(V ,E)$. So, the minimum weight perfect matching problem can be ...
• 443
1 vote
125 views

### Preference based assignment problem to maximize utility

I am studying an optimization problem which can be recast as an LP I have described below. I wish to understand the structure of optimizers of the original problem by studying the optimizers of the LP....
• 11
145 views

### Budgeted min cost max flow in bipartite where the flows must also be a matching set

I'm trying to find a problem description that is roughly akin to a budgeted min-cost max-weight bipartite matching where the capacities are greater than 1. Imagine a max-flow problem on a graph that ...
38 views

### Pattern Matching Variant Problem

Given string P with length n, and a function A on P [n] --> [n] that does the following: For every 1 <= k <= n A on P [k] = { the maximum index i such that P[1...i] = P[k...k+i-1] Write an ...
1 vote
159 views

### pairing numbers and intervals

subject: pairing numbers and intervals Let NUMBERS be a list of n integer numbers. The numbers are listed in no specific order. ...
83 views

### Lights-out! on a hex grid with buttons on nodes and lights on faces

Consider a truncated hexagonal grid, with some hexagons lit up, such as the one shown below: Here the red hexagons are lit up while the dark gray hexagons are not lit up. The grid has buttons (small ...
• 5,892
57 views

### For a regular bipartite graph with vertices $X\cup Y$, prove that $|S|\leq|n(S)|$ $\forall S\subseteq X$

As the title states, we are given a bipartite undirected graph $G=(X\cup Y,E)$ such that every vertex $v\in V$ satisfies $d(v)=k$ for a constant $k$. The general goal of the proof is to show that ...
• 365
1 vote
42 views

### Assign items from inventory to people maxmizing the number of satisfied people

We have a set of people, and each person has a list of wished items (not unique, they could want multiple copies of each item). We have an inventory of items that we want to assign to the people. We ...
• 111
1 vote
76 views

### Choosing root for maximum matching in tree

This question deals with how to find the maximum matching in a tree. I understood the answers, but for one part. Choose a root arbitrarily. For each subtree, calculate the maximum matching within the ...
• 160
26 views

### Analyzing Parallel Matching Algorithm - Why it takes O(n+m) time and work?

Using the algorithm provided by this paper, they said that: The algorithm defines a single phase of the local max algorithm. Each step of the phase takes at most O(log(m + n)) = O(logn) time and O(n +...
21 views

### What is the associative operator ⊕ in graph matching? and How does it works?

I read a paper about Parallel Matching, and I didn't understand what the associative operator ⊕ in the following lemma/proof and how does it works in vertices and edges in the graph? Lemma 3. Using ...
• 1
1 vote
40 views

• 75
63 views

### Size of the maximum matching in arbitrary graph

I am asked to find a probabilistic algorithm to determine the size of the maximum matching of an arbitrary simple undirected graph $G$. My claim is that, it is equivalent to find a global min cut on ...
• 159
1 vote