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