- Vivi Padova
- Il Bo
Wednesday 19 January 2011 h. 14:30, room 2BC30
Yuri Faenza (Dip. Mat.)
"The maximum matching problem and one of its generalizations"
Given a graph G(V,E), a matching M is a subset of E such that each vertex in V appears as the endpoint of at most one edge from M. The maximum matching problem and its weighted counterpart are among the most important and studied problems in combinatorial optimization. In this talk, we survey a number of classical results on the topic and present a new algorithm for a non-trivial generalization of the maximum weighted matching problem. The talk will be accessible to a general audience.
Rif. int. C. Marastoni, T. Vargiolu