Pagina Radice del Progetto: Ricerca Casualizzata di 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.
Come prima fase del progetto, vogliamo implementare un algoritmo per la ricerca del matching massimo tramite un algoritmo randomizzato. Per fare ciò intendiamo utilizzare come un oracolo l'algoritmo randomizzato che decide per l'esistenza di un accoppiamento perfetto (accoppiamento che interessa tutti i nodi del grafo).
Come seconda fase del progetto, eseguiamo un lavoro sperimentale per verificare che l'algoritmo risponda correttamente con la probabilità da noi dichiarata.

Come riferimento, consiglio:

Papadimitriou, Christos H.
Computational complexity.
Wiley-Interscience Series in Discrete Mathematics and Optimization.
Addison-Wesley Publishing Company, Reading, MA, 1994.
ISBN 0-201-53082-1

Volendo intrapprendere un percorso più ambizioso, esiste la possibilità di compiere questo stesso percorso, ma per grafi non necessariamente bipartiti.

Geelen, James F.
An algebraic matching algorithm.
Combinatorica 20 (2000), no. 1, 61--70.

created: 25 Aprile 2001
updated: 25 Aprile 2001