Optimum branchings
Open accessAbstract
An arborescence T is a tree whose edges a re directe d so that eac h is directed toward a differe nt node.Exactly one node of T, called the root , has no edge of T directed toward it.Le t C be any directe d grap h with a real numerical weight on eac h edge.A good algorithm is described for find ing in C (if there is one) a s panning arborescence, with prescribed root, whose ed ges have maximum (o r minimum) total weight.
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
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.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Identity-by-descent fragments shorter than 5 cM are prone to false positives because of insufficient SNPs.
“Fragments shorter than this length are prone to false positives due to insufficient SNPs90–92.”
From Paths and timings of the peopling of Polynesia inferred from genomic networks (2021) · cites this paper as [91]
Section 3 describes an algorithm for optimum branchings in weighted graphs, and Section 9 discusses spanning arborescences; page numbers are unavailable in our copy. Searches for identity-by-descent fragments, 5 cM, SNPs, and false positives found no passage addressing the claim. (LLM, conf=0.78)
Experimental — accuracy not yet measuredIBD length distributions are right-truncated at 15 cM because longer outlier segments are expected to come from recent contact less than 10 generations ago.
“The distributions are also right truncated at 15 cM, because outlier segments longer than this are expected to stem from recent contact, dating to less than 10 generations ago (18th century or later) as computed from the expected generation time (g) based on a single fragment length ℓ in Morgans, Egℓ≃32ℓ/1M, where 1M is one Morgan91.”
From Paths and timings of the peopling of Polynesia inferred from genomic networks (2021) · cites this paper as [91]
Section 4 describes an algorithm for maximum-weight branchings in directed graphs, and Section 2 discusses spanning arborescences; neither addresses genetic segments. Searches for IBD, 15 cM, centimorgans, and generation time found no passage supporting the truncation or dating claim. (LLM, conf=0.79)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
On the shortest spanning subtree of a graph and the traveling salesman problem
Kruskal, J. B. (1956) · Proceedings of the American Mathematical Society · doi:10.1090/s0002-9939-1956-0078686-7 · Cited by 5,173 · see citing works
Edmonds, J. (1965) · Canadian Journal of Mathematics · doi:10.4153/cjm-1965-045-4 · Cited by 2,428 · see citing works
Self-citationMatroids and the greedy algorithm
Edmonds, J. (1971) · Mathematical Programming · doi:10.1007/bf01584082 · Cited by 889 · see citing works
Self-citationRosenstiehl, P. (1966) · HAL (Le Centre pour la Communication Scientifique Directe) · Cited by 19 · see citing works
The Traveling Salesman Problem
Körte, B., & Vygen, J. (2018) · Algorithms and combinatorics · doi:10.1007/978-3-662-56039-6_21 · Cited by 16 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Snitkin, E. S., Zelazny, A. M., Thomas, P. J., Stock, F., Program, N. C. S., Henderson, D. K., Palmore, T. N., & Segre, J. A. (2012) · Science Translational Medicine · doi:10.1126/scitranslmed.3004129 · Cited by 863 · see citing works
Paths and timings of the peopling of Polynesia inferred from genomic networks
Ioannidis, A. G., Blanco-Portillo, J., Sandoval, K., Hagelberg, E., Barberena-Jonas, C., Hill, A. V. S., Rodríguez-Rodríguez, J. E., Fox, K., Robson, K., Haoa-Cardinali, S., et al. (2021) · Nature · doi:10.1038/s41586-021-03902-8 · Cited by 124 · see citing works
- Authors
- Edmonds, J.
- Affiliations
- National Institute of Standards and Technology (US)
- Corresponding author
- Edmonds, Jack
- ORCID
- Edmonds, Jack
- Venue
- Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics
- Published
- 1967-10
- Volume
- 71B
- Issue
- 4
- Pages
- 233
- ISSN
- 0022-4340 (ISSN-L)
- OpenAlex
- W4246185962
- Cited by
- 731
- References
- 5
- Citations by year
- 2026: 13 · 2025: 21 · 2024: 24 · 2023: 35 · 2022: 18 · 2021: 41 · 2020: 40 · 2019: 22 · 2018: 51 · 2017: 27 · 2016: 23 · 2015: 28 · 2014: 33 · 2013: 33 · 2012: 27
- FWCI
- 0.00
- Type
- journal article
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- public-domain
- Locations
- Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics (publishedVersion, public-domain)
- National Institute of Standards and Technology (NIST) (submittedVersion, public-domain)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Graph Theory and Algorithms
- Physical Sciences › Engineering › Control and Systems Engineering › Optimization and Mathematical Programming
- Keywords
- spanning arborescences, directed graphs, edge weights
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
