Pagina Radice del Progetto: Accoppiamento Bipartito

Dato un grafo bipartito (semplice e non orientato) G=(V,E), un matching è un insieme M di archi di G che non condividano alcun nodo. Un matching vien detto massimo se la sua cardinalità |M| è massima.
Vogliamo trovare un matching massimo in al più $O(n\sp {1/2}m)$ passi, dove n = |V| ed m = |E|.
Inoltre, qualora siano dati dei pesi sugli archi, vogliamo trovare un matching massimo che abbia peso minimo (Il peso di un matching resta definito come somma dei pesi degli archi che lo costituiscono).

Come riferimento, sia per il caso di cardinalità che per quello pesato, consiglio:

Cook, William J.; Cunningham, William H.; Pulleyblank, William R.; Schrijver, Alexander
Combinatorial optimization.
Wiley-Interscience Series in Discrete Mathematics and Optimization.
A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1998.
ISBN: 0-471-55894-X

Per il caso di cardinalità è possibile partire dal lavoro originale.

Hopcroft, John E.; Karp, Richard M.
An $n\sp{5/2}$ algorithm for maximum matchings in bipartite graphs.
SIAM J. Comput. 2 (1973), 225--231.
abstract: To obtain a maximum matching, the algorithm proceeds in a sequence of phases. At the beginning of each phase, the algorithm has a matching M. During each phase the algorithm finds a maximal set of vertex-disjoint minimum length augmenting paths for M and increases the matching along each of these paths. The authors prove that $O(n\sp {1/2})$ of these phases suffice for finding a maximum matching, even in nonbipartite graphs. The authors also show how to execute each phase of the algorithm in $O(m)$ time. Consequently, the running time of their algorithm is $O(n\sp {1/2}m)$.

created: 25 Aprile 2001
updated: 25 Aprile 2001