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

146 questions
Filter by
Sorted by
Tagged with
21 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)$ ...
13 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 -> ...
106 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 ...
89 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: ...
24 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 ...
696 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 ...
35 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 ...
12 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 ...
52 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 ...
57 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.
26 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, ...
56 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 ...
27 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
17 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 ...
81 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 ...
105 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 ...
148 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\...
33 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 ...
35 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 ...
20 views

### Online bipartite matching problem for task assignment

I have $n$ drivers, each one has a balance (in Us dollars), availability status (true if he is not working already) and number of accomplished tasks in the current ...
133 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 ...
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 ...
27 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 ...
88 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 ...
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 ...
109 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 ...
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 ...
36 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 ...
50 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 ...
43 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 ...
133 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-...
118 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 ...
873 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 ...
157 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 ...
60 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?
136 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.
74 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 ...
63 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 ...
67 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?
200 views

### Christofides algorithm (by hand) (suboptimal solution - is it my fault?)

I would like to calculate an eularian path using Christofides algorithm on this graph: (Focus on the first number in each box representing the distance) $\alpha$ denotes the start and end vertex of ...
67 views

### Stable matching with asymmetric arrays (gale shapley)

I was reading this thread The stable marriage algorithm with asymmetric arrays and started to solve the problem asked in this thread about matching 5 students with 10 dorms. One of the answer ...
354 views

### Why does this greedy algorithm fail to accurately determine whether a graph is a perfect matching?

I came across this problem in Tim Roughgarden's course on Coursera: In this problem you are given as input a graph $T=(V,E)$ that is a tree (that is, $T$ is undirected, connected, and acyclic). A ...
125 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 ...
45 views

### Maximizing quantities/length in buckets to match each other

I have a use case, real one, and I'm trying to come up with an efficient maximization algorithm to solve it. I'll try to simplify, with a simple analogue, and after will explain the real world use ...
27 views

### Determine whether two collections of items can be paired

Given collections I (items) and S (slots), where I >= S. And a pairing function that ...
65 views

### Obtaining Max-Weight Matching from Max-Weight-Max-Cardinality Matching?

I have a graph with integer-valued edge weights (possibly negative) on which I would like to obtain a maximum-weight matching. However, I am using python-graph-tool, which only has max-cardinality ...
846 views

### Algorithm for matching people

I work at a summer camp where one of the activities is called Speed Dating. It's a game where participants talk with each other for a fixed amount of time. At the end everyone has to list three people ...
387 views

### Which algorithm can calculate an optimal allocation of students to projects?

I am trying to find an algorithm which calculates an optimal and stable allocation of $n$ students to $m$ projects, where each student strictly ranks all projects by preference. The available projects ...
This is part of a bigger proof I'm trying to solve, which eventually came down to one thing: Let $G=(V,E)$ an un-directed, complete, metric graph (maintains the triangle inequality) with an even ...