Reports
An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs ; CU-CS-062-75 Public Deposited
Downloadable Content
Download PDF
https://scholar.colorado.edu/concern/reports/pr76f415f
- Abstract
- A matching on a graph is a set of edges, no two of which shared a vertex. A maximum matching contains the greatest number of edges possible. This paper presents an efficient implementation of Edmonds’ algorithm for finding a maximum matching. The computation time is proportional to V^3, where V is the number of vertices; previous implementation of Edmonds’ algorithm have computation time proportional to V^4. The implementation is based on a system of labels that encodes the structure of alternating paths.
- Creator
- Date Issued
- 1975-03-01
- Academic Affiliation
- Last Modified
- 2019-12-21
- Resource Type
- Rights Statement
- Language
Relationships
Items
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
anEfficientImplementationOfEdmondsAlgorithmForMaximumMat.pdf | 2019-12-21 | Public | Download |