Canadian Journal of Mathematics · 1965 · 2.4K citations · 5 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsSet TheoryCombinatorial OptimizationCombinatorial Set TheoryEnumerative CombinatoricsGraph AlgorithmsGraph TheoryMatching TheoryGeometric MatchingGraph MatchingMatching AlgorithmsMatching ProblemsMatchings EnumerationMaximum Matching ApproximationTree Algorithms
A graph is a finite set of vertices and edges, with each edge joining two vertices, and a matching is a set of edges that share no vertices. The study aims to present an efficient algorithm for computing a maximum‑cardinality matching in a graph. The algorithm efficiently identifies a maximum‑cardinality matching in any given graph.
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.
5
The Factorization of Linear Graphs
W. T. Tutte · Journal of the London Mathematical Society · 1947 · 939 citations
The Theory of Graphs and its Applications.
F. Harary, Claude Berge · Biometrika · 1963 · 605 citations
Claude Berge · Proceedings of the National Academy of Sciences · 1957 · 574 citations · Full text