Grafos Bipartidos
(Desculpem a bagunça de links e referências, depois eu arrumo direitinho)
Definição
http://en.wikipedia.org/wiki/Bipartite_graph
Maximum matching
- http://en.wikipedia.org/wiki/Hopcroft–Karp_algorithm
- http://www.cse.iitb.ac.in/~sundar/cs435/lecture23.pdf
- http://stackoverflow.com/questions/6366516/how-does-the-hopcroft-karp-algorithm-work
Ou você pode modelar um fluxo (que tem complexidade equivalente ao Hopcroft-Karp se você usar o Dinic – http://en.wikipedia.org/wiki/Dinic%27s_algorithm)
Minimum Vertex Cover
Problemas:
Minha solução: http://pastebin.com/bpHNYTw8
Maximum Independent Set
http://en.wikipedia.org/wiki/Vertex_cover_problem – "A set of vertices is a vertex cover, if and only if its complement is an independent set."
page revision: 3, last edited: 17 Sep 2012 17:57