The bipartite-matching tag has no wiki summary.
1
vote
0answers
30 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 ...
1
vote
1answer
36 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 ...
3
votes
1answer
71 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 ...
4
votes
1answer
111 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 ...
4
votes
1answer
73 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 ...
0
votes
1answer
64 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 ...
1
vote
1answer
247 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 ...
2
votes
1answer
68 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 ...
7
votes
2answers
153 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|)$?
