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.
174
questions
0
votes
0answers
24 views
Is there an approximation algorithm for the three-person stable roommates problem?
While there's an algorithm for solving the stable roommates problem, I understand that the three-people-per-room version of that problem, sometimes called the "threesome roommates problem", ...
0
votes
1answer
24 views
Matching with specific cardinality
In a weighted graph $G(\mathcal{V},\mathcal{E})$ where $w(i,j)$ is the weight of the edge $(i,j) \in \mathcal{E}$. How can I find a maximum weighted matching with a specific size (i.e specific ...
0
votes
0answers
28 views
Gale-Shapley Stable matching where one man's preference list changes
Given $n>1$ women and men. Let $M$ be the stable matching given by the Gale-Shapley algorithm with men proposing. Is there a stable matching instance such that:
changing one man's preference list ...
0
votes
0answers
31 views
Computing a fractional matching of maximum product in a bipartite graph
Given a bipartite graph $(X\cup Y, E)$ with edge weights, it is easy to find a matching in which the product of weights is maximum: replace each edge weight with its logarithm, and find a matching in ...
1
vote
2answers
35 views
Maximum matching for general graph
I am studying the maximum matching problem and I was trying to understand why the classical augmenting path algorithm does not work for the general graph (i.e. for non bipartite graph) and you must ...
1
vote
1answer
51 views
Can't wrap my head around on building a suffix table for Boyer Moore
My resources were the following video, as well as this video.
Basically, in one of the videos they state that the good suffix table for the pattern "ABCBAB" is the following:
k
suffix
d2
1
...
2
votes
1answer
70 views
maximum cardinality weighted matching
I am looking for a reference for maximum cardinality weighted matching and the best running time algorithm for it.
Maximum Cardinality Weighted Matching: Given an undirected weighted graph $G(\mathcal{...
2
votes
1answer
141 views
Find optimal local alignment of two strings with restrictions
I have a homework question that I trying to solve for many hours without success, maybe someone can guide me to the right way of thinking about it.
The problem:
We want to find an optimal local ...
0
votes
0answers
37 views
Maximum cardinality matching of maximum weight
Given a graph, I want to find the matching with the maximum size in terms of edges, but among those matchings, given a real weight function on the edges, the one with the maximum weight. Is there an ...
1
vote
1answer
22 views
Concept of M-augmenting path to find a larger matching than $M$
I'm reading section 16.1 of the book, Combinatorial optimization, Polyhedra and efficiency by Schrijver. Here, he starts with a matching $M$ and describes a path $P$ that is $M$-augmenting if:
The ...
1
vote
1answer
24 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 ...
4
votes
2answers
67 views
How difficult is this matching-like problem?
Let $A$ and $B$ be two sets of integers with $|A|>|B|$.
Given a map $f: A \rightarrow B$ and $i \in A, j \in B$, let us use the shorthand "$i$ is matched to $j$" if $f(i)=j$. I am ...
3
votes
1answer
190 views
Game on the graph with matchings
The game on the graph $G$ is defined as follows. Initially, the chip is located at one of the vertices (let's call it the starting one). The players take turns, on each move it is necessary to move ...
-1
votes
1answer
25 views
Maximal vs maximum matchings
Let $M_1$ be an inclusion-maximal matching in $G$ (that is, there is no matching which strictly contains it), and $M_2$ a maximum-size matching in $G$. How to prove that $|M_2| \le 2|M_1|$?
1
vote
1answer
41 views
Independent sets into which all the vertices of the graph can be split
How to prove that if $G$ is an acyclic transitive digraph, then the least independent sets into which all vertices of G can be divided is equal to the size of the longest paths to $G$?
0
votes
0answers
25 views
Set of cycles in directed graph
I have a directed graph. How to find in it some set of cycles that are pairwise
do not intersect, but cover the entire set of vertices, if a cycle from one vertex is not considered a cycle, but cycle ...
1
vote
1answer
29 views
Maximum one-to-many matching
Let $G = (X+Y,E)$ be a bipartite graph and $k\geq 1$ an integer. A maximum $k$-matching is a subset of $E$ in which each vertex of $X$ is adjacent to at most $k$ edges and each vertex of $Y$ is ...
3
votes
1answer
49 views
Combinatorial Problem similar in nature to a special version of max weighted matching problem
I have a problem and want to know if there is any combinatorial optimization that is similar in nature to this problem or how to solve this special version of the max weight matching problem.
I have a ...
0
votes
0answers
47 views
Why did Hopcroft and Karp write $M_0, M_1, M_2, \cdots, M_i, \cdots$? (Hopcroft - Karp Algorithm)
I am reading āAn $n^{\frac{5}{2}}$ Algorithm for Maximum Matchings in Bipartite Graphsā by Hopcroft and Karp.
Please see the image below.
Let $s$ be the cardinality of a maximum matching.
I think any ...
3
votes
1answer
191 views
Weighted Online Matching - randomized algorithms
Let's consider the edge weighted online matching problem.
The Vertices arrive online and reveal all their current edges and edge-weights $w_e>0$. The goal is to maximize the matchings weight. An ...
1
vote
1answer
41 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 ...
3
votes
0answers
21 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
86 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
23 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
23 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
65 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
89 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
80 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
19 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
60 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
2answers
98 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
30 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
34 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)$ ...
2
votes
1answer
567 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
403 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
38 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
1k 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 ...
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
61 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.
2
votes
0answers
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 ...
1
vote
1answer
39 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
4
votes
1answer
90 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
168 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
266 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
44 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
354 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
25 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 ...
