Reports
Using Blossoms to Find Maximum Matchings on Graphs ; CU-CS-056-74 Public Deposited
https://scholar.colorado.edu/concern/reports/kd17ct72k
- Abstract
- A matching on a graph is a set of edges, no two of which shared a vertex. The problem discussed is to find a matching with the greatest number of edges possible. An algorithm is presented that implements the concept of blossoms, as developed by Edmonds, completely and efficiently. The computation time is proportional to V^3. The algorithm can be used in an algorithm that computes maximum weighted matchings efficiently.
- Creator
- Date Issued
- 1974-09-01
- Academic Affiliation
- Last Modified
- 2019-12-21
- Resource Type
- Rights Statement
- Language
Relationships
Items
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
usingBlossomsToFindMaximumMatchingsOnGraphsCuCs05674.pdf | 2019-12-21 | Public | Download |