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-graphs
Search options not deleted
user 31310
A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that no two vertices in the same set are adjacent.
1
vote
0
answers
53
views
Optimal preprocessing in the Kuhn-Munkres algorithm
The matrix formulation of the Kuhn-Munkres algorithm for solving the Linear Assignment Problem requires a preprocessing in which the minimal values of a line be subtracted from every value in that lin …
- 13.2k
1
vote
0
answers
16
views
Complexity of optimal cartesian matching
Question:
what is known about the algorithmic aspects of optimally matching a set $\mathcal{P} = \prod\limits_{i=1}^n \left(1,\,\cdots,\,k_i\right)$ of grid-points to a set of $\prod\limits_{i=1}^nk_ …
- 13.2k
3
votes
Accepted
An variation of an assignment problem in combinatorics: assign items to customers
That is a classical assignment problem, that can also be solved with the Kuhn-Munkres algorithm, for which generalizations to rectangular assignment matrices exist.
- 13.2k
2
votes
Accepted
Minimum number of perfect matchings in a regular bipartite graph
as already mentioned in the comments,
that is answered by Alexander Schrijver in his publication "Counting 1-factors in regular bipartite graphs":
any $k$-regular bipartite graph with $2n$ vertices h …
- 13.2k
2
votes
Solving assignment problem using Hungarian method vs min cost max flow problem
I would prefer the Hungarian method in cases, where a simpler algorithm and a simpler data structure seem desirable; that could be the case, if only small instances need to be handled or, if a GPU imp …
- 13.2k