Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with bipartite-matching
Search options questions only
not deleted
user 1342
4
votes
1
answer
385
views
Find a maximum matching that saturates a given set of vertices
In an unweighted bipartite graph $G = (X + Y,E)$, we would like to find a maximum matching, but among all those maximum matchings, we would like to find one that saturates a given subset $X_0\subseteq …
- 6,164
1
vote
1
answer
39
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 i …
- 6,164
4
votes
1
answer
308
views
Term for a matching which is perfect on one side only
What is a standard term for a matching in a bipartite graph, in which one part has less vertices than the other part, and the part with less vertices is fully matched (but the other part is, obviously …
- 6,164
1
vote
2
answers
192
views
Either find a perfect matching, or return a witness that none exist [duplicate]
I am looking for a polynomial-time algorithm that takes as input a bipartite graph $(X\cup Y, E)$, and returns one of two options:
If a perfect matching exists, it returns the matching;
Otherwise, i …
- 6,164
2
votes
1
answer
1k
views
Using LP to prove the max matching - min cover theorem
Konig's theorem says that, in a bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover. This theorem has several proofs; I would like to know if the following pr …
- 6,164
4
votes
1
answer
227
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 - …
- 6,164
1
vote
1
answer
13
views
FInding a maximum-weight matching that is substantially larger than the second-best
Given a weighted complete bipartite graph, there are well-known polytime algorithms for finding a maximum-weight perfect matching. I am interested in comparing the weight of a perfect matching with t …
- 6,164
2
votes
2
answers
42
views
Can a perfect matching always be found by a picking sequence?
There are $n$ people and $n$ items. For each person, there is a set of items he likes. Our goal is to give to each person a single item that he likes, i.e, find a perfect matching in the preference gr …
- 6,164
1
vote
1
answer
231
views
Maximum-cardinality matching in unbalanced bipartite graphs
Let $G = (X+Y, E)$ be a bipartite graph, and suppose we want to find a maximum-cardinality matching in $G$.
The Hopcroft-Karp algorithm runs in time $O(|E|\sqrt{|V|})$, where here $|V| = |X|+|Y|$. So …
- 6,164
1
vote
0
answers
93
views
Stable matching of producers, consumers and objects
Has the following version of the stable matching problem been studied?
There are $k$ types of objects.
There are $n$ producers, each of whom can produce a single object of any type, and has a persona …
- 6,164
4
votes
1
answer
120
views
Term for a graph decomposition based on a maximum matching
Let $M$ be a maximum cardinality matching in a bipartite graph $G(X+Y,E)$. Let $X_0$ be the subset of $X$ unmatched by $M$. Define the following sequence:
$Y_1 = $ the neighbors of $X_0$ using edges …
- 6,164