About the optimal algorithms on matching - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>CS - 计算机科学

About the optimal algorithms on matching

About the optimal algorithms on matching# CS - 计算机科学

d*g2005-09-14 07:09

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*e2005-09-14 07:09

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*g2005-09-14 07:09

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*e2005-09-14 07:09

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.