d*******g
发帖数: 36 | 1 Hi, guys,
Could anyone tell me about the optimal or fast known algorithms on maximum
bipartite matching and maximum weighted bipartite matching?
I mean their time complexities.
Thanks in advance. |
l******e
发帖数: 153 | 2 hungarian is O(N^3)
【在 d*******g 的大作中提到】
: Hi, guys,
: Could anyone tell me about the optimal or fast known algorithms on maximum
: bipartite matching and maximum weighted bipartite matching?
: I mean their time complexities.
: Thanks in advance.
|
d*******g
发帖数: 36 | 3
But it seems there are algorithms with O(|E|\sqrt(|V|)) for maximum bipartite
matching and algorithms with O(|V|*(|E|+|V|log|V|)) for its weighted version.
【在 l******e 的大作中提到】
: hungarian is O(N^3)
|
l******e
发帖数: 153 | 4 that's right, I didn't mean hungary is the fastest. thought it is frequently
used. maybe the best thing is that you can find online code for it :)
bipartite
version.
【在 d*******g 的大作中提到】
:
: But it seems there are algorithms with O(|E|\sqrt(|V|)) for maximum bipartite
: matching and algorithms with O(|V|*(|E|+|V|log|V|)) for its weighted version.
|
