Reports
An Efficient Implementation of Edmonds' Algorithm for Maximum Weight Matching on Graphs ; CU-CS-075-75 Public Deposited
https://scholar.colorado.edu/concern/reports/hx11xf95h
- Abstract
- A matching on a graph is a set of edges, no two of which share a vertex. If each edge of the graph has a number, called its weight, a maximum weight matching has the greatest total weight possible. An algorithm with run-time 0(V^3), where V is the number of vertices, is presented. It is based on Edmonds’ algorithm, which has run-time 0(V^4). The algorithm uses efficient data structures for blossoms and for choosing edges in a search.
- Creator
- Date Issued
- 1975-08-01
- Academic Affiliation
- Last Modified
- 2019-12-21
- Resource Type
- Rights Statement
- Language
Relationships
Items
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
anEfficientImplementationOfEdmondsAlgorithmForMaximumWei.pdf | 2019-12-21 | Public | Download |