Matchings, covers, and stars
| dc.contributor.author | Heier, Heather | |
| dc.date.accessioned | 2019-04-17T18:08:11Z | |
| dc.date.available | 2019-04-17T18:08:11Z | |
| dc.date.graduationmonth | May | |
| dc.date.issued | 2019-05-01 | |
| dc.description.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. | |
| dc.description.advisor | Nathan Albin | |
| dc.description.degree | Master of Science | |
| dc.description.department | Department of Mathematics | |
| dc.description.level | Masters | |
| dc.identifier.uri | http://hdl.handle.net/2097/39562 | |
| dc.language.iso | en_US | |
| dc.publisher | Kansas State University | |
| dc.rights | © the author. This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s). | |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | |
| dc.subject | Perfect matching | |
| dc.subject | Edge cover | |
| dc.subject | Stars | |
| dc.subject | BipartiteMatching | |
| dc.title | Matchings, covers, and stars | |
| dc.type | Report |
