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.
157
questions
3
votes
0answers
13 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 ...
0
votes
0answers
15 views
A request for literature on Matching your partner problem
I need reference for a good book (a title and an author will do) or reference on the web which explains the problem of matching procedures of suitable partners between several
males and females based ...
1
vote
1answer
80 views
Are these problems NP-Complete?
I got 2 decision problem that I need to answer if they are in P or they are NP complete:
1.Just like subset sum:
given the integers or natural numbers ${\displaystyle w_{1},\ldots ,w_{n}}$ does ...
0
votes
0answers
22 views
Stable matching with dynamic preference lists
I have a set $F$ of $n_1$ families, a set $C$ of $n_2$ children ($n_1<n_2$) and a set $M$ of feasible one-to-one matchings of the families with the children. All the children have the same ...
1
vote
0answers
18 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 ...
0
votes
0answers
46 views
Special case of stable marriage
I have an instance of the stable marriage problem in which the first side $S_1$ has $n_1$ agents and the second side $S_2$ has $n_2$ agents with $n_2$ is very big in comparison to $n_1$. In addition, ...
0
votes
0answers
24 views
Options for approaching stable marriage problem with unequally sized sets of elements/preferences
I am looking for an algorithm/code that will provide stable matching for two unequally sized sets of elements (clubs and students) with an unequal set of preferences. There is a large pool of students ...
3
votes
1answer
75 views
Selecting k rows and k columns from a matrix to maximize the sum of the k^2 elements
Suppose $A$ is an $n \times n$ matrix, and $k \ge 1$ is an integer. We want to find $k$ distinct indices from $\{1, 2, \ldots, n\}$, denoted as $i_1, \ldots, i_k$, such that
$\sum_{p, q = 1}^k A_{...
0
votes
0answers
14 views
Algorithm for b-matching on bipartite graph [duplicate]
I have a bipartite graph, where I want to assign nodes in Left set to Right set of nodes. There is a "b" constraint, which limits the maximum possible node degrees on the Right set.
Since it is a ...
-1
votes
1answer
21 views
Best and Worst options in Gale Shapley algorithm for an agent
Please consider the figure below. I have to find the best and worst options for W. From the preference list of W, the best option for W is D but there is no matching of W with D in all the 6 options. ...
1
vote
1answer
62 views
An algorithm to find the closest match between 2 arrays of RGB pixel tuples
So I'm looking for a bit of an abstract algorithm and I'd appreciate any references to read up on. This is a bit tough to explain but I'll try my best.
Suppose we have 2 arrays of ...
0
votes
1answer
16 views
Problem with understanding two sided Matching Algorithm: maximium cardinality
I am trying to understand the maximum cardinality problem in the context of stable matching algorithm. I am reading the following article at the link:
A Two-Sided Matching Decision Model Based on ...
2
votes
0answers
25 views
Blossom's Algorithm or Maximal Matching [closed]
I am given a complete weighted graph and I need to make pairs among the vertices so that the sum of weights is maximum.
(If I have vertices $v1, v2, v3, v4$ and if I make pairs $(v1,v2)$ and $(v3,v4)$ ...
0
votes
0answers
17 views
Relation between shape descriptors and featured connected component in matching problems
Hope I'm asking in the correct community, from the title, I need a clarification regarding the idea of dealing with 3d descriptor and featured connected components.
I have this approach: model -> ...
2
votes
1answer
317 views
one-to-many matching in bipartite graphs?
Consider having two sets $L$ (left) and $R$ (right).
$R$ nodes have a capacity limit.
Each edge $e$ has a cost $w(e)$.
I want to map each of the $L$ vertices to one node from $R$ (one-to-many ...
1
vote
1answer
277 views
How to find maximum matching edges in undirected tree
Let $B$ be an undirected tree with $|V|$ nodes given as adjacency list. I want to develop a greedy algorithm using pseudo code to find a maximal matching in runtime $\mathcal{O}(|V|)$.
My approach:
...
3
votes
1answer
30 views
Computing minimum partition of poset of $N$ intervals into chains in $o(N^{2.5})$ time?
Consider a set $P$ of $N$ intervals $\{I_i = (l_i, r_i)\}$ partially ordered according the standard interval order: $I_i < I_j$ iff $r_i \le l_j$.
I want to find a minimum cardinality partition of ...
4
votes
1answer
776 views
A problem with the greedy approach to finding a maximal matching
Suppose I have an undirected graph with four vertices $a,b,c,d$ which are connected as in a simple path from $a$ to $d$, i.e. the edge set $\{(a,b), (b,c), (c,d)\}$. Then I have seen the following ...
1
vote
0answers
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 ...
0
votes
0answers
15 views
Maximum cardinality bipartite matching when nodes are ordered and only subsets can be matched?
Maximum bipartite matchine problem can be converted to the maximum flow problem and it can be solved by Edmonds-Karp algorithm in O(VE)<=O(V^3). But there can be bounded problem, when the nodes on ...
2
votes
1answer
56 views
Matching each unique pokemon with a unique move
Background:
There are 832 unique Pokemon in the Pokemon universe, and
There are 728 fighting moves that the Pokemon can collectively learn.
No Pokemon can learn to do every fighting move, and some ...
1
vote
1answer
58 views
Give an example of a connected graph where Ī±(G) =100 and Ī²(G) = 200
So I need to find a form of a graph such that its vertex cover is twice that of its matching, but I am running into problems brainstorming, I know K3 is of this form, but not one at such a magnitude.
0
votes
0answers
30 views
Counting step in Gale-Shapley Algorithm(Deferred Acceptance Algorithm)
Imagine there is a modified version of many-to-one school choice matching with Deferred Acceptance Algorithm(DAA): other things will be the same as original DAA, except that for an unassigned student, ...
2
votes
0answers
59 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 ...
1
vote
1answer
38 views
Prove that any tree contains a matching of size |InternalNodes|/2 [closed]
How can i prove that any tree contains a matching of size |InternalNodes|/2?
Thanks in advance
0
votes
0answers
32 views
Matching algorithm to find pattern match in rectangles
I am trying to write an algorithm to find the best (if any) match for a pattern of rectangles. Essentially, given a database of three different arrays of rectangles. The color is irrelevant here, it's ...
4
votes
1answer
85 views
Term for a graph decomposition based on a maximum matching
Let $M$ be a maximum cardinality matching in a bipartite graph $G(X+Y,E)$. Let $X_0$ be the subset of $X$ unmatched by $M$. Define the following sequence:
$Y_1 = $ the neighbors of $X_0$ using edges ...
2
votes
0answers
139 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 ...
4
votes
1answer
212 views
Matching Algorithm - How to maximize matched quantity with unique matching rules?
Given a set $S=\{A,B,\cdots,H\}$. Elements in $S$ can be matched according to the following rules:
$$\begin{aligned}
A\leftrightarrow B\\
C\leftrightarrow D\\
B+C\leftrightarrow F\\
D+A\...
4
votes
1answer
38 views
How to construct an ordinary matching from a fractional matching?
Given a graph $G=(V,E)$. A fractional matching, say $f$, assigns every edge $e \in E$ to a fraction $f(e) \in [0,1]$, with the constraint: for $v \in V$, $\sum_{e \ni v}f(e) \leq 1 $.
My question ...
1
vote
0answers
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 ...
2
votes
0answers
250 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 ...
1
vote
0answers
23 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 ...
0
votes
0answers
29 views
Bipartite vertex cover [duplicate]
If this link can be any help
https://codeforces.com/blog/entry/63164
A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set.
A ...
1
vote
0answers
110 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 ...
5
votes
3answers
1k views
What is a fractional matching?
For the maximum matching problem, we can find the fractional matching which I understand involves some sort of weighting for the edges. However, I cannot seem to find an exact and simple explanation ...
0
votes
0answers
132 views
Maximum matching blossom algorithm
https://stanford.edu/~rezab/classes/cme323/S16/projects_reports/shoemaker_vare.pdf
Why do we use blossom contrast in maximum matching?
The examples that I have seen can easily be solved by just ...
3
votes
2answers
44 views
Minimizing catastrophic risk in Gale-Shapley matching
In the hospital-resident assignment problem we have to match a large set of med students with a small set of hospitals. Hospitals may accept multiple students, but the number of students is much ...
0
votes
0answers
40 views
Find maximal matching in tree in $O\left(\frac{n}{\log n}\right)$
As any tree can be described as a binary sequence ($i$-th bit is 0 if the edge goes down and 1 otherwise, every edge is travelled twice $-$ up and down, so such sequence's length is $2 |V| - 2$), any ...
1
vote
0answers
93 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 ...
4
votes
1answer
56 views
Can maximum matching algorithms be used for maximum weight matching?
There are two fast algorithms for maximum matching on general graphs:
Micali and Vazirani in $O(E\sqrt{V})$.
Mucha and Sankowski in $O(V^{2.376})$.
Can these be also used for maximum weighted ...
2
votes
1answer
169 views
Find a minimum-weight perfect b-matching, where b is even
How would one find a minimum-weight perfect b-matching of a general graph, where the number of edges incident on each vertex is a positive even number not greater than b?
A minimum-weight perfect b-...
1
vote
1answer
151 views
Find a minimum-weight perfect 2-matching
How would one find a minimum-weight perfect 2-matching of a general graph? Is it possible to use standard matching techniques like Blossom V?
A minimum-weight perfect 2-matching of a graph G is a ...
4
votes
1answer
2k views
Maximum matching using linear programming
In a bipartite graph $G = (V,E)$, there is a neat algorithm for finding a maximum matching (or even a maximum-weight matching) using linear programming. It is explained here. The first step is to ...
4
votes
2answers
207 views
Run-time of Hungarian algorithm - matrix formulation
There are many different explanations of the Hungarian algorithm. My favorite explanation is the one based on matrices, for example here, since it is very intuitive and easy to carry out in a ...
0
votes
1answer
75 views
Minimal edge cover of the hypergraph
We know that minimal edge cover for the normal graph is polynomial time solvable.
Is it also true for hypergraph?
0
votes
1answer
246 views
minimum cardinality maximal matching of graph
How to find minimum cardinality maximal matching?
I tried that pick a edge from highest degree vertex remove other edges from same vertex and so on.
1
vote
2answers
81 views
Either find a perfect matching, or return a witness that none exist [duplicate]
I am looking for a polynomial-time algorithm that takes as input a bipartite graph $(X\cup Y, E)$, and returns one of two options:
If a perfect matching exists, it returns the matching;
Otherwise, it ...
1
vote
2answers
76 views
Two Problems in understanding the algorithm for computing shortest paths in undirected graphs with possibly negative edge weights
Section 2 of this Lecture Note: Shortest Path Algorithms Luis Goddyn, Math 408 describes an algorithm using Edmonds' Minimum Weight Perfect Matching Algorithm to solve the shortest path problem for ...
0
votes
1answer
91 views
Minimum perfect matching with uneven vertices?
Given this graph, what is the minimum perfect matching? What do you do, when there is an uneven number of vertices?
