Algoritmos para emparelhamentos em grafos bipartidos
Herbert Alexander Baier Saip
DISSERTAÇÃO
Português
T/UNICAMP Sa28a
Campinas, SP : [s.n.], 1993.
181 f. : il.
Orientador : Claudio Leonardo Lucchesi
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação
Resumo: O problema de emparelhamentos em grafos consiste em determinar um conjunto M de arestas do grafo, onde as arestas são disjuntas nos vértices. Em particular, estamos interessados em determinar emparelhamentos máximos, ou seja, de cardinalidade máxima. Existem muitas variações em torno do...
Ver mais
Resumo: O problema de emparelhamentos em grafos consiste em determinar um conjunto M de arestas do grafo, onde as arestas são disjuntas nos vértices. Em particular, estamos interessados em determinar emparelhamentos máximos, ou seja, de cardinalidade máxima. Existem muitas variações em torno do tema, o grafo pode ser: bipartido ou não, ponderado ou não. Neste trabalho apresentamos as principais técnicas para se projetar os algoritmos mais eficientes que resolvem o problema de emparelhamentos máximos, ponderados ou não, em grafos bipartidos. Também descrevemos os principais algoritmos, seqüenciais e paralelos, que resolvem este problema. O Capítulo 2 apresenta os principais algoritmos para resolver o problema em grafos bipartidos não ponderados: o algoritmo de Hopcroft e Karp, o algoritmo paralelo de Kim e Chwa e o algoritmo paralelo de Goldberg, Plotkin e Vaidya. O Capítulo 3 apresenta os principais algoritmos para resolver o problema em grafos bipartidos ponderados: o algoritmo de Edmonds e Karp, o algoritmo com escalonamento de Gabow, o algoritmo com escalonamento e aproximação de Gabow e Tarjan, o algoritmo paralelo de Goldberg, Plotkin e Vaidya e o algoritmo paralelo de Gabow e Tarjan. O Apêndice A contém uma tabela dos principais algoritmos para resolver o problema no caso em que os grafos não são bipartidos
Ver menos
Abstract: 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...
Ver mais
Abstract: 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
Ver menos
Algoritmos para emparelhamentos em grafos bipartidos
Herbert Alexander Baier Saip
Algoritmos para emparelhamentos em grafos bipartidos
Herbert Alexander Baier Saip
Exemplares
Nº de exemplares: 3
Não existem reservas para esta obra