Algoritmos para emparelhamentos em grafos bipartidos

AUTOR(ES)
DATA DE PUBLICAÇÃO

1993

RESUMO

The matching problem in graphs consists in determining a vertex disjoint set M of edges of the graph. In particular, we are interested in finding maximum matchings, that is, matchings of maximum cardinality. There are many variations around this problem, the graph can be: bipartite or general, weighted or not. In this work we present the main techniques to design the most efficient algorithms that solve the problem of maximum matching, weighted or not, in bipartite graphs. We also describe the main algorithms, sequential and parallel, to solve this problem. Chapter 2 contains the most important algorithms to solve the problem for non weighted bipartite graphs, namely, the algorithm of Hopcroft and Karp, the parallel algorithm of Kim and Chwa, and the parallel algorithm of Goldberg, Plotkin and Vaidya. Chapter 3 contains the most important algorithms to solve the problem for weighted bipartite graphs, namely, the algorithm of Edmonds and Katp, the scaling algorithm of Gabow, the scaling and approximation algorithm of Gabow and Tarjan, the parallel algorithm of Goldberg, Plotkin and Vaidya and the parallel algorithm of Gabow and Tarjan. In Appendix A it is given a table which describes briefly the most important algorithms for solving the general problem, in which the graph is not bipartite

ASSUNTO(S)

algoritmos grafo (sistema de computador)

ACESSO AO ARTIGO

Documentos Relacionados