# 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.

218 questions
Filter by
Sorted by
Tagged with
59 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,772
48 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 ...
• 293
1 vote
30 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
27 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 ...
• 121
20 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 +...
20 views

### How does parallel marching algorithm work?

For the following graph and graph representation: V set: An array of n elements, where each entry V[i] = Pj<i deg(vj). A set: An adjacency array representation of a graph, where entries A[V[i]] ...
• 1
19 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
33 views

### How to assign people to take part in an activity with limited space, with some people having priority over others

I am trying to solve a seemingly straightforward problem, for which a well-known algorithm should exist, but I can't find it. Imagine we have an activity, let's say football/soccer. Obviously, only 11 ...
• 101
1 vote
36 views

• 75
49 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 ...
• 149
1 vote
497 views

### How to determine if a tree $T = (V, E)$ has a perfect matching in $O(|V| + |E|)$ time

This is a problem I've come across while studying on my own; it's from Algorithms by Papadimitriou, Dasgupta and Vazirani. Specifically, the problem statement is: Give a linear-time algorithm that ...
1 vote
706 views

### How can we express value of cosine similarity of two documents into percentage?

We were doing project work for plagiarism checking. For this purpose, we have taken a term frequency vector of two documents and measured the similarity using a cosine similarity measure. The value of ...
78 views

### Maximum matching with social distancing

Let $G = (X\cup Y, E)$ be a bipartite graph. Suppose $X$ contains people, $Y$ contains seats in a theatre, and each edge $(x,y)$ has a weight representing how much person $x$ is willing to pay for ...
• 5,768
141 views

### Maximum-weight matching with a bounded number of fractional edges

In graphs with odd cycles, the maximum weight of a fractional matching may be higher than that of a standard matching. For example, in a cycle of length 3, where all edges have weight 1, the maximum-...
• 5,768
74 views

### Algorithm best compare similarities between two data sets in percentage

I'm trying to create an algorithm that finds the percentage of similarity between two subjects with sets of survey questions. Example: Q1: Do you prefer physically demanding tasks? A1: Nope Maybe Yes -...
• 101
1 vote
71 views

### Hardness result for online matching

Currently studying the following paper: "Fair Allocation in Online Markets" - Gollapudi and Panigrahi 2014 In which they present Theorem 2 as a hardness result for online maxmin matchings (...
145 views

• 2,891
1 vote
75 views

### Can somebody please explain what are these variables doing here?

I have this algorithm: I understand overall what's happening here, we're shrinking the blossoms (odd cycles) to end up with a bipartite matching problem, and then opening them again to get a maximum ...
• 121
description of the algorithms behavior I have two strings s1 and s2, with $len\_s1 <= len\_s2$. I would like to find the ...