Paths, Trees, and Flowers
- 1 January 1965
- journal article
- Published by Canadian Mathematical Society in Canadian Journal of Mathematics
- Vol. 17, 449-467
- https://doi.org/10.4153/cjm-1965-045-4
Abstract
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.Keywords
This publication has 5 references indexed in Scilit:
- Covers and packings in a family of setsBulletin of the American Mathematical Society, 1962
- Some recent applications of the theory of linear inequalities to extremal combinatorial analysisProceedings of Symposia in Applied Mathematics, 1960
- An algorithm for a minimum cover of a graphProceedings of the American Mathematical Society, 1959
- TWO THEOREMS IN GRAPH THEORYProceedings of the National Academy of Sciences, 1957
- The Factorization of Linear GraphsJournal of the London Mathematical Society, 1947