Paths, Trees, and Flowers

Canadian Journal of Mathematics - Tập 17 - Trang 449-467 - 1965
Jack Edmonds1
1National Bureau of Standards and Princeton University

Tóm tắt

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.

Từ khóa


Tài liệu tham khảo

10.1112/jlms/s1-22.2.107

Ford, 1962, Flows in networks

10.1090/S0002-9939-1959-0106853-5

Witzgall, 1965, Modification of Edmonds﹜ algorithm for maximum matching of graphs, 69B

Berge, 1962, The theory of graphs and its applications

10.1090/S0002-9904-1962-10791-5

10.1090/psapm/010/0114759

Edmonds, 1965, J. Res. Natl. Bureau Standards, 69B

10.1073/pnas.43.9.842

Thông tin
Thông tin xuất bản

Canadian Journal of Mathematics

Tập 17

449-467

Thông tin tác giả