Questions tagged [bipartite-matching]
The bipartite-matching tag has no usage guidance.
114
questions
0
votes
0answers
506 views
Hopcroft–Karp algorithm time complexity
In the last 2 paragraphs of the paper about Hopcroft–Karp algorithm to find the maximum cardinality matching in bipartite graph:
https://dl.dropboxusercontent.com/u/64823035/04569670.pdf
The ...
4
votes
3answers
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 ...
3
votes
1answer
733 views
Number of Matchings in a Bipartite
Given two sets A and B of sizes |A| = n and |B| = m, where m >= n.
There are edges from set A to set B.
I need to find the number of matchings where all of vertices ...
4
votes
2answers
1k views
Bipartite Graph Game
So say we have a bipartite graph G=(X,Y,E). Let's make a game out of it.
I go first. I pick a node in X. You go next. You pick a node in Y that is connected by an edge to the node I picked. Next it's ...
5
votes
2answers
521 views
In the Hopcroft-Karp algorithm, what is the purpose of the breadth first search?
In the Hopcroft-Karp algorithm for bipartite matching, I don't understand the purpose of the breadth first search. I think it's used to find a set of vertex disjoint augmenting paths, but I'm not ...
3
votes
1answer
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 ...
4
votes
1answer
393 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 ...
7
votes
1answer
4k 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$...
4
votes
1answer
138 views
Bipartite graph question
Assume you are given a bipartite graph $G = (U, V, E)$ and you are given an integer $n$. Assume also that for each $v \in V$, you are given two integers $v_{min}$ and $v_{max}$ (where $v_{min} \le v_{...
0
votes
1answer
137 views
Graph Bipartiteness
I have 2 questions regarding Bipartiteness with corresponding examples.
1) Can a non-connected graph be bipartite if it has an isolated vertex? Let's take the following graph:
I would say YES with ...
4
votes
2answers
6k 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.
...
3
votes
1answer
939 views
Clarification with Kuhn-Munkres/Hungarian Algorithm
I have been attempting to get my mind around the Kuhn-Munkres/Hungarian Algorithm. I have been using the following statement of the algorithm which I found here.
Based on my readings on the algorithm,...
2
votes
1answer
336 views
Matching girls with boys without mutual attraction (variant of maximum bipartite matching)
Let us say you have a group of guys and and a group of girls. Each girl is either attracted to a guy or not, and vice versa. You want to match as many people as possible to a partner they like.
Does ...
9
votes
2answers
612 views
Size of Maximum Matching in Bipartite Graph
Am I correct in my observation that the cardinality of the maximum matching $M$ of a bipartite graph $G(U, V, E)$ is always equal to $\min(|U|, |V|)$?
