Questions tagged [bipartite-matching]
The bipartite-matching tag has no usage guidance.
172
questions
0
votes
1
answer
49
views
Convert a Graph to a Good Graph using Maximum Matching in Bipartite Graphs Algorithm
Consider a graph $ G = (V, E) $ where a vertex $ v \in V $ is designated as the center if it is connected to every other vertex $ u \in V $, such that both $ uv $ and $ vu $ are present in $ E $. A ...
1
vote
1
answer
36
views
Finding a matching with a specific weight
Polynomial-time algorithms for finding a maximum-weight matching in a weighted graph are well-known. Suppose I want not the maximum-weight matching, but a matching with a specific weight given as an ...
- 6,132
0
votes
1
answer
29
views
Optimizing Pairings Between Integers and Intervals for Maximal Matching
Consider the scenario where we are given a collection of n integers. These integers are unordered and may include duplicates. Additionally, we have a set of m ranges, each defined by two integers ...
2
votes
1
answer
54
views
Why does Hopcroft-Karp only work on bipartite graphs?
I have a simple question which I cannot answer, and it relates to this question.
What I cannot answer is this:
Why does a graph with bidirectional edges destroy the "bipartiteness" of the ...
- 155
2
votes
1
answer
63
views
Weighted bipartite maximum cost with a fixed number of vertices
Having a complete bipartite graph with parts $A$ and $B$, which is edge-weighted, is there a way to compute a subgraph with the maximum sum of all weights and:
Only a constant number $n$ of vertices ...
- 21
0
votes
0
answers
20
views
flow network, class and classroom matching
Problem:
given a set of classes and classrooms, then given a set M of pairs (a,b), which means it is valid assignment from class a to classroom b(ex:(c,2), (c,3), (d,2), means class c can be assigned ...
1
vote
1
answer
195
views
Greedy Maximum Bipartite Matching
To find the maximum matching on a bipartite graph, I propose the following greedy algorithm:
At each iteration, pick an unmatched vertex with the smallest degree and match it to one of it's neighbours ...
- 11
1
vote
1
answer
126
views
Expected maximum matching size in a random bipartite graphs
What is the expected maximum matching size of a bipartite graph $(A\cup B, V)$ where $\lvert A\rvert = n$ and $\lvert B\rvert = n$ and the probability of a edge existing between $A$ and $B$ is a fixed ...
- 25
2
votes
1
answer
84
views
Dinitz’ algorithm in simple unit-capacity networks
I am studying for an algorithm design course, and can't understand this demonstration about how Dinitz’ algorithm computes a maximum flow in $O(m \sqrt{n})$ time.
This is what is written on the slides ...
1
vote
0
answers
32
views
Find an assignment discarding a subset of possible assignments
We have a $N \times N$ cost matrix where the cost denotes the amount incurred for assigning a worker to a task.
The number of possible assignments is $N!$. Let us call this set of all possible ...
- 11
0
votes
1
answer
42
views
A bipartite maxiumum matching problem, fitting a ratios vector on the resulting subset
Statement of problem
We have two sets of vertices, $V$ and $U$, each of which has a vector of attributes $A$.
The set of edges $E$ is defined such that there is an edge $vu\in{E}$ between vertices $v$ ...
- 101
1
vote
1
answer
42
views
Schoolclass Optimization Algorithm for finding Stable Matching
I have the task to write a program that puts students in classes and that in the best possible way.
We have given the name, the foreign language a student chooses(french or latin), a profile (Music,...
- 13
1
vote
1
answer
89
views
Bipartite matching with constraints on one part
We have a bipartite graph with parts $A$ and $B$, and it is edge weighted. We have some constraints for part $B$. Each constraint is in this format: Between vertices $b_1$ and $b_2$ both from part $B$,...
1
vote
0
answers
62
views
What is the name of this matching problem?
We have a bipartite graph consisting of parts $A$ and $B$. Each vertex $i$ of part $A$ has weight $w_i$ and capacity $c_i$. We say a vertex $i$ in part $A$ is satisfied if at least $c_i$ adjacent ...
0
votes
0
answers
136
views
Budgeted min cost max flow in bipartite where the flows must also be a matching set
I'm trying to find a problem description that is roughly akin to a budgeted min-cost max-weight bipartite matching where the capacities are greater than 1. Imagine a max-flow problem on a graph that ...
