Pagina Radice del Progetto: Accoppiamento di Massima Cardinalità in Grafo non Bipartito

Dato un grafo (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.

Come riferimento, 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

La lettura del lavoro originale, se da un lato non dovrebbe aiutare nella codifica, resta istruttiva ed è comunque un classico.

Edmonds, Jack
Paths, trees, and flowers.
Canad. J. Math. 17 1965 449--467.

Volendo strafare, ma non ne vedo davvero la necessità, uno potrebbe implementare l'algoritmo cha al momento detiene il record di complessità.

Peterson, Paul A. and Loui, Michael C.
The general maximum matching algorithm of Micali and Vazirani.
Algorithmica 3 (1988), no. 4, 511--533.
abstract: The authors give a clear exposition of the complicated $O(n\sp {1/2}m)$ maximum matching algorithm of S. Micali and V. Vazirani [21st Annual Symposium on Foundations of Computer Science (Syracuse, NY, 1980), 17--27, IEEE, New York, 1980].
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. J. E. Hopcraft and R. M. Karp [SIAM J. Comput. 2 (1973), 225--231] proved that $O(n\sp {1/2})$ of these phases suffice for finding a maximum matching, even in nonbipartite graphs. Each phase of the algorithm runs in $O(m)$ time. Consequently, the running time of the algorithm is $O(n\sp {1/2}m)$.

created: 25 Aprile 2001
updated: 25 Aprile 2001