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