Matchings, covers, and stars

Abstract

This report relates four important problems of combinatorial optimization on graphs: the maximum matching problem, the minimum edge cover problem, the maximum perfect matching problem, and the minimum perfect matching problem. Although polynomial time algorithms exist for each of these problems in general, they all become much simpler on bipartite graphs due to an interesting relationship to the stars on such a graph.