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.

49 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
157 views

Complexity of removing edges to eliminate a perfect matching

Suppose $G$ is a bipartite graph which has a perfect matching. I want to find the fewest number of edges to delete from $G$ so that a perfect matching no longer exists. What is the complexity of this ...
139 views

variant of the stable roommates problem

The Stable Roommates Problem matches 2n participants into n sets of roommates based off of each participant's list of preferences. I was wondering if there was a variant of this problem where the ...
17 views

How to generate a uniform random sample of unique vertex pairings from a undirected graph under constraint?

I'm working on a research project where I have to pair up entities together and analyze outcomes. Normally, without constraints on how the entities can be paired, I could easily select one random ...
136 views

Edmond's Blossom algorithm (Maximum Matching) explanation

I asked this question on Math Stackexchange but it didn't get much attention, so I am asking it here. Edmond's Blossom algorithm (Wikipedia), or simply the blossom algorithm, is a popular graph ...
535 views

Optimal pairing of points in a set

I have an even number of points, each with coordinates $(x, y, z)$. I need to group these points into pairs. The cost of pairing two points is the Euclidean distance between them. I'd like to find the ...
55 views

Properties of the filtered preference list (phase 1) in the Stable Roommates problem

I'm currently working my way through An Efficient Algorithm for the “Stable Roommates” Problem by Robert Irving (Journal of Algorithms, 6:577–595, 1984). On page 7 the paper starts with ...
148 views

Construct matching for half of the vertices, in linear time

Suppose we have a graph $G=(V,E)$ connected and $K_{1,3}$-free. Sumner proved that every claw-free connected graph with an even number of vertices has a perfect matching (so, it is maximum matching). ...
93 views

Hardness of a special case of maximum matching

Input: A set of $n$ Users $U=\{u_1, ..., u_n\}$ and a set of $m$ products $I=\{i_1, ..., i_m\}$. Associated with each pair $u \in U$ and $i \in I$ is the probability $p_{u,i}$ of $u$ purchasing the ...
61 views

Matching of two weighted graphs allowing one-to-many mapping

I am looking for a heuristic for a graph matching problem as follows. Given two graphs: $A$ (consisting of nodes $a_i$) and $B$ (consisting of nodes $b_i$). Typically the size of $B$ is larger than ...
154 views

Maximum weighted matching for directed (non-bipartite) graphs

This post concerns mainly non-bipartite graphs. Edmonds (1961) have proposed the Blossom algorithm to solve the maximum matching problem for undirected graphs. The best implementation of it is due ...
298 views

Perfect matching in complete, weighted graph

I'm trying to find pairs in a complete, weighted graph, similar to the one below (weights not shown). For each possible pair there is a weight and I would like to find pairs for including all ...
33 views

22 views

splitting of people betwen groups with group prioritiy list per person

Looking for an algorithm for splitting a list of people (S) into groups (G), |S| <= |G|, more than one person wants to be in a certain group. Every person has a monotone ranking from highest (most ...
36 views

Is there such a problem as b-Matching with different b values?

Consider a bipartite Garph $G=(L \cup R, E)$. Naturally, a b-Matching problem is to find a set of edges $M \subset E$, such that each node in $L$ and $R$ are adjuscent to maximum $b$ neighbors, and a ...
21 views

Blossom Algorithm

I have noticed that in the blossom algorithm, we need to find the blossom while finding the augmenting path. What will happen if I just know there is a blossom in a graph and the contracted graph has ...
40 views

String matching problem needed some explanation

This is a question from CLRS book. (Chapter 32, string matching, the question is the problem for the whole chapter, it's in the end of the chapter) Let $y^i$ denote the concatenation of string y ...
37 views

Online Many-to-one Matching

Offline Problem I have a graph $\mathcal{G} = (\mathcal{D} \cup \mathcal{A}, \mathcal{E})$. Each edge $e \in \mathcal{E}$ between the two vertex sets $\mathcal{D}$ and $\mathcal{A}$ has an ...
24 views

Optimal matching of individuals in vehicles

I am looking for an algorithm to find the optimal matching/allocation of n individuals in m identical vehicles. The aim is to create groups of individuals who will share these vehicles. Groups' size ...
116 views

Find a minimum weight matching of a specific size

Given a positive-weighted complete graph $G=(V,E)$ and an even integer $k$, I want to find a minimum weight matching of size exactly $k$, i.e., I want to choose $k/2$ vertex disjoint edges such that ...
99 views

Computing a shortest $M$-alternating walk (for the Blossom algorithm)

When explaining the Blossom algorithm for maximum (nonbipartite) matchings, Shrijver describes, given a simple graph $G = (V,E)$, a matching $M \subseteq E$, and the set $X \subseteq V$ of nodes ...