Hello!
My question is simple. Can someone give me a test sample for maximum matching in bipartite graphs on which Kuhn's algorithm preforms badly (something like O(N * M) in time). Thanks in advance.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
Hello!
My question is simple. Can someone give me a test sample for maximum matching in bipartite graphs on which Kuhn's algorithm preforms badly (something like O(N * M) in time). Thanks in advance.
Название |
---|
In a complete bipartite graph, Kuhn's would traverse the longest augmenting path first: http://imgur.com/a/dXXRq
It seems to be 1 + 2 + ... + N = O(N2) in that case
It will take longest time if it fails to augment the matching. Then it will have to look through all edges in adjacency lists of reachable nodes. So we take a full bipartite graph with n/4 + n/4 nodes and another n/2 nodes connect to any node in the right half, m=n^2/16+n/2. Ignoring the part where we find matching in full part the total number of times we will look at some edge is n/2 (m-n/2+1) = O(nm)