Hostname: page-component-7b7567c8c-m6dxt Total loading time: 0 Render date: 2026-11-18T23:21:52.958Z Has data issue: false hasContentIssue false

Paths, Trees, and Flowers

Published online by Cambridge University Press:  20 November 2018

Jack Edmonds*
Affiliation:
National Bureau of Standards and Princeton University
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A graph G for purposes here is a finite set of elements called vertices and a finite set of elements called edges such that each edge meets exactly two vertices, called the end-points of the edge. An edge is said to join its end-points.

A matching in G is a subset of its edges such that no two meet the same vertex. We describe an efficient algorithm for finding in a given graph a matching of maximum cardinality. This problem was posed and partly solved by C. Berge; see Sections 3.7 and 3.8.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1965