Matchings, covers, and stars
Date
2019-05-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
Matching, Perfect matching, Edge cover, Stars, Bipartite
Graduation Month
May
Degree
Master of Science
Department
Department of Mathematics
Major Professor
Nathan Albin
Date
2019
Type
Report
