Questions tagged [bipartite-matching]
The bipartite-matching tag has no usage guidance.
16
questions
6
votes
2
answers
1k
views
Finding a subset in bipartite graph violating Hall's condition
We are given a bipartite graph of $n \leq 200$ vertices in both the first and the second partite set. Let $U$ be some set of vertices in the first set, and $V$ those vertices from the second that are ...
- 187
5
votes
2
answers
9k
views
The stable marriage algorithm with asymmetric arrays
I have a question about the stable marriage algorithm, for what I know it can only be used when I have arrays with the same number of elements for building the preference and the ranking matrices.
...
- 163
7
votes
1
answer
6k
views
How to find the maximum independent set of a directed graph?
I'm trying to solve this problem.
Problem: Given $n$ positive integers, your task is to select a maximum number of integers so that there are no two numbers $a, b$ in which $a$ is divisible by $b$...
- 255
4
votes
3
answers
2k
views
Number of ways to fill a 2xN grid with M colors
This question was asked in the onsite regionals for ACM ICPC 2013 at Amritapuri.
In short, the question asked to find the number of ways to fill a $ 2\times N$ grid with $M$ colors such that no two ...
- 273
4
votes
1
answer
4k
views
Stable marriage problem with only one side having preferences [duplicate]
I was wondering about a variation on the Stable Marriage Problem. Initially, we have two sets of entities, usually males and females, and they have preference lists ranking the other group, and ...
- 143
1
vote
1
answer
492
views
Weighted Matching with multiple assignments and min assignments
I need to do a weighted matching between two sets (say students and professors). The set of students is much larger than set of professors. So multiple students can be matched to professors. However, ...
- 141
7
votes
1
answer
533
views
Given 2 sets of n points: minimize sum of traveled distances
I am given two sets $S, T$ each of $n$ points in $\mathbb{R}^k$, I want to find a bijection $a : S \rightarrow T$, such that $$\sum_{s \in S} d(s, a(s))$$ gets minimized, with $d$ being the Euclidean ...
- 783
5
votes
1
answer
535
views
Decomposing a bipartite graph of maximal degree d to d matchings
I have tried for the last few days to prove that any bipartite graph of maximal degree d may be broken into (at most) d matchings.
My main approach is to prove this inductively over the maximal ...
- 51
5
votes
3
answers
1k
views
Maximum number of matched vertexes in a one-to-many bipartite graph
I have a variant of bidding problem at hand.
There are N bidders(~20) who bid for items from a pool of many items(~10K). Each bidder can bid many items. I want to maximize the number of bidders who ...
- 53
4
votes
1
answer
189
views
Finding a subset with few neighbors
Given a bipartite graph $G(X+Y,E)$, how can I find a non-empty subset $Y'\subseteq Y$, such that $|N(Y')| \leq |Y'|$ (where $N$ is the set of neighbors)?
If $|Y|\geq |X|$ then the problem is easy - $...
- 5,894
4
votes
1
answer
2k
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, ...
- 43
4
votes
1
answer
435
views
Assignment problem with no cost
I have a problem that I was able to conceptualize as following:
Problem
We have a set of n people. And m subsets representing their ethnicity like White, Hispanic, Asian etc. Given any combination of ...
- 41
3
votes
1
answer
2k
views
Existence of bipartite perfect matching
Let $B = G(L, R, E)$ be a bipartite graph. I want to find out whether this graph has a perfect matching. One way to test whether this graph has a perfect matching is Hall's Marriage Theorem, but it is ...
- 478
2
votes
1
answer
1k
views
Polynomial time solution for bipartite matching
Inspired by this StackOverflow question, I am wondering if there is an efficient algorithm for the following problem:
Assume $n$ items and $n$ boxes, with all boxes numbered numerically and all ...
- 201
2
votes
1
answer
1k
views
Determining the minimum vertex cover in a bipartite graph from a maximum flow/matching using the residual network rather than alternating paths
Wikipedia shows how one can determine the minimum vertex cover in a bipartite graph ($G(X \cup Y, E)$) in polytime from a maximum flow using alternating paths. However, I read that the (S,T) cut (...
1
vote
1
answer
745
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:
...
user106782