Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-22T16:05:55.647Z Has data issue: false hasContentIssue false
  • English
  • Français

Paths, Trees, and Flowers

Published online by Cambridge University Press:  20 November 2018

Jack Edmonds
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.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 17 , 1965 , pp. 449 - 467
Copyright
Copyright © Canadian Mathematical Society 1965

References

1. Berge, C., Two theorems in graph theory, Proc. Natl. Acad. Sci. U.S., 43 (1957), 842–4.Google Scholar
2. Berge, C., The theory of graphs and its applications (London, 1962).Google Scholar
3. Edmonds, J., Covers and packings in a family of sets, Bull. Amer. Math. Soc, 68 (1962), 494–9.Google Scholar
4. Edmonds, J., Maximum matching and a polyhedron with (0, 1) vertices, appearing in J. Res. Natl. Bureau Standards 69B (1965).Google Scholar
5. Ford, L. R. Jr. and Fulkerson, D. R., Flows in networks (Princeton, 1962).Google Scholar
6. Hoffman, A. J., Some recent applications of the theory of linear inequalities to extremal combinatorial analysis, Proc. Symp. on Appl. Math., 10 (1960), 113–27.Google Scholar
7. Norman, R. Z. and Rabin, M. O., An algorithm for a minimum cover of a graph, Proc. Amer. Math. Soc, 10 (1959), 315–19.Google Scholar
8. Tutte, W. T., The factorization of linear graphs, J. London Math. Soc, 22 (1947), 107–11.Google Scholar
9. Witzgall, C. and Zahn, C. T. Jr., Modification of Edmonds﹜ algorithm for maximum matching of graphs, appearing in J. Res. Natl. Bureau Standards 69B (1965).Google Scholar