Questions tagged [bipartite-matching]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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|)$?