Document Type

Technical Report

Publication Date

Fall 9-1-1974

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.

Share

COinS