The DOI matches its Crossref record; 6 of the 6 references it cites were found in a registry or an index.
Paths, Trees, and Flowers
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The Factorization of Linear Graphs
Tutte, W. T. (1947) · Journal of the London Mathematical Society · doi:10.1112/jlms/s1-22.2.107 · Cited by 945
The Theory of Graphs and its Applications.
Harary, F., & Berge, C. (1963) · Biometrika · doi:10.2307/2333777 · Cited by 603
Berge, C. (1957) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.43.9.842 · Cited by 577
Some recent applications of the theory of linear inequalities to extremal combinatorial analysis
Hoffman, A. J. (1960) · Proceedings of symposia in applied mathematics · doi:10.1090/psapm/010/0114759 · Cited by 192
An algorithm for a minimum cover of a graph
Norman, R. Z., & Rabin, M. O. (1959) · Proceedings of the American Mathematical Society · doi:10.1090/s0002-9939-1959-0106853-5 · Cited by 115
Covers and packings in a family of sets
Edmonds, J. (1962) · Bulletin of the American Mathematical Society · doi:10.1090/s0002-9904-1962-10791-5 · Cited by 101
Self-citation
Research works printed but not linked: 3
- Ford, 1962, Flows in networks
- Witzgall, 1965, Modification of Edmonds﹜ algorithm for maximum matching of graphs, 69B
- Edmonds, 1965, J. Res. Natl. Bureau Standards, 69B
Cited by
Sorted by citations
Assembly of long, error-prone reads using repeat graphs
Kolmogorov, M., Yuan, J., Lin, Y., & Pevzner, P. A. (2019) · Nature Biotechnology · doi:10.1038/s41587-019-0072-8 · Cited by 5,986
Surface codes: Towards practical large-scale quantum computation
Fowler, A. G., Mariantoni, M., Martinis, J. M., & Cleland, A. N. (2012) · Physical Review A · doi:10.1103/physreva.86.032324 · Cited by 3,059
An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
Hopcroft, J. E., & Karp, R. M. (1973) · SIAM Journal on Computing · doi:10.1137/0202019 · Cited by 2,799
Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
Edmonds, J., & Karp, R. M. (1972) · Journal of the ACM · doi:10.1145/321694.321699 · Cited by 2,531
Self-citationDowsland, K. A., & Thompson, J. M. (2012) · Springer eBooks · doi:10.1007/978-3-540-92910-9_49 · Cited by 2,470
Metadata
- Authors
- Edmonds, J.
- Affiliations
- National Institute of Standards and Technology (US)
- Corresponding author
- Edmonds, Jack
- ORCID
- Edmonds, Jack
- Venue
- Canadian Journal of Mathematics
- Publisher
- Canadian Mathematical Society
- Published
- 1965
- Volume
- 17
- Pages
- 449-467
- ISSN
- 0008-414X (ISSN-L)
- 1496-4279
- OpenAlex
- W4233756358
- Cited by
- 2,428
- References
- 6
- Citations by year
- 2026: 80 · 2025: 108 · 2024: 100 · 2023: 110 · 2022: 126 · 2021: 107 · 2020: 134 · 2019: 118 · 2018: 110 · 2017: 91 · 2016: 84 · 2015: 72 · 2014: 83 · 2013: 80 · 2012: 73
- FWCI
- 0.83
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Canadian Journal of Mathematics (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Graph Theory and Algorithms
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Advanced Graph Theory Research
- Keywords
- maximum matching, graph theory, matching algorithms, trees, paths, graph algorithms
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
