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.

Filter by
Sorted by
Tagged with
0
votes
0answers
12 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
65 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
54 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
118 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
30 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
32 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 ...
0
votes
0answers
11 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 ...
0
votes
0answers
44 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
19 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
23 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 ...
0
votes
0answers
59 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 ...
4
votes
3answers
832 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
84 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
41 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
30 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
35 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 ...
3
votes
1answer
34 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
77 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
59 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
273 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
95 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
40 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
74 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
61 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
46 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
39 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?
2
votes
2answers
143 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 ...
0
votes
1answer
52 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 ...
3
votes
2answers
219 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 ...
3
votes
0answers
98 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 ...
3
votes
1answer
40 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 ...
3
votes
1answer
26 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 ...
1
vote
1answer
39 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 ...
2
votes
1answer
560 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 ...
2
votes
1answer
145 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 ...
0
votes
0answers
47 views

Hopcroft und Karp Algorithm and a suitable representation for a graph

Hey Guys I have a small question about the Hopcroft and Karp Algorithm. I have a task to solve where I have to calculate the perfect matching. My professor told me I should use the Hopcroft Algorithm....
4
votes
1answer
95 views

Is a perfect matching's weight less than MST of a metric graph?

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 ...
3
votes
1answer
93 views

Students in classroom problem - Flow in network

I have room, which is opened some days in week, in different hours each day. I have multiple students, each has time some days in week, in different hours. Each student have to visit the room ...
2
votes
2answers
35 views

Can a perfect matching always be found by a picking sequence?

There are $n$ people and $n$ items. For each person, there is a set of items he likes. Our goal is to give to each person a single item that he likes, i.e, find a perfect matching in the preference ...
0
votes
0answers
20 views

Is implementation of approximate dynamic maximal matching feasible?

I'm wondering if algorithms described in: https://ieeexplore.ieee.org/abstract/document/7782946/ http://drops.dagstuhl.de/opus/volltexte/2014/4845/ easy to implement. They seem to mention the word "...
1
vote
1answer
37 views

Group tuples to satisfy constraints

This is a problem that involves matching students with various skills into groups so that there are as many groups as possible while ensuring that each group has certain skills present. I've reduced ...
1
vote
0answers
172 views

Best algorithm to generate matchmaking pairs

I am trying to come up with a matchmaking algorithm based on player ratings for my game, and I am pretty sure the algorithm I have is not the best (or maybe doesn't even work), but have no idea how to ...
1
vote
1answer
444 views

Which algorithm for game matchmaking in tournament

I organize amateur tournaments every week with random players. Every week, players sign up, and I get a list with: Name Rank (1, 2 or 3) Role (s) (DPS, TANK and HEALER) I need to get balanced teams ...
2
votes
1answer
953 views

Perfect matching in a bipartite regular graph in linear time

Given a $G=(V,E)$ bipartite, undirected, 4-regular graph, I would like to find a perfect matching in linear time. It is easy to show that there is a perfect matching for the graph, by using flow and ...
4
votes
1answer
459 views

Changing preference in Gale-Shapley algorithm?

Suppose, in the context of the classic marriage problem, two equal size groups of $n$ men and $n$ women are being matched, with the GS algorithm. If a man were to switch the order of a pair of women, ...
0
votes
2answers
47 views

maximum matching number decreases when vertices collapse?

It seems that the maximum matching number decreases when some independent (not connected) vertices collapse into one vertex, but I don't know if it is absolutely true. Would maximum matching number ...
7
votes
0answers
99 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 ...
0
votes
1answer
31 views

Decide if there is a sbugroup of edges in graph that every vertex meets exactly k edges from subgroup

I've been trying to solve the following question: Show a polynomial algorithm for the following problem. Let $G = (V, > E)$ a graph. The goal is to decide if there is $E' ⊆ E$ , such that for ...
1
vote
2answers
567 views

Stable matching problem is greedy or Dynamic?

Is the stable matching problem greedy or Dynamic ? Please anyone can give a strong explanation as i tried to find it on the net but it isn't available.
0
votes
1answer
742 views

How to use stable matching algorithm in order to determine optimal schedule?

This is a problem 1.6 from the book Algorithm Design by Kleinberg/Tardos: There's a company that manages ships that do various tasks when in port. There're $n$ ships, $n$ ports, $m$ days in a month ...