This problem on UVA was categorized under bipartite matching. I am not able to figure any algorithm for this. If we make a graph, where edge denotes that 2 people can form a couple, wouldn't the problem be of maximum independent set ?? It would be really great if someone can give some hint about this.
Thanks
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
Independent set is not NP problem for biparite graph. You can prove that answer always is V — |maximal matching|. I'm not ready to prove this fact now.
As a proof: In general graphs Independent set = V — minimal vertex cover. You can prove that minimal vertex cover is maximal matching in bipartite graphs. It's called [Konig's theorem](http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory)) and it's a proof there, too.
minimal vertex cover is maximal matching in bipartite graphs
How about isolated vertexes? They increse the minimal vertex cover, but don't change the maximal matching.
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=392&page=show_problem&problem=3642
Heyy, can you tell how is this a bipartite graph ?
That's problem 'cover graph with minimal number of paths', doesn't it?
UPD: acyclic graph
Nothing
http://www.spoj.com/problems/ANGELS/
Can you please explain how do we construct a bipartite graph in this ? Thanks