Maximal Flow Through a Network¶
Ford, L. R., & Fulkerson, D. R. (1956). Maximal Flow Through a Network. Canadian Journal of Mathematics, 8, 399-404.
Cited by¶
3 citations across 3 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Cut
- First, cuts identify bottlenecks: by the max-flow min-cut theorem, the maximum flow from a source to a sink equals the capacity of the minimum cut separating them, so a system's throughput is decided by its narrowest separating link-set, every other edge being slack relative to that bottleneck.
This sourceProves the max-flow min-cut theorem: maximum s–t flow equals minimum s–t cut capacity, localizing throughput onto the narrowest separating edge-set.
Supported in partVerified against the publisher's abstract
The paper is the primary source on maximal flow in a capacitated network, but the text retrieved (landing-page furniture plus the abstract) states the flow problem only, not the max-flow min-cut equality or the bottleneck gloss.
“The problem discussed in this paper was formulated by T. Harris as follows: “Consider a rail network connecting two cities by way of a number of intermediate cities, where each link of the network has a number assigned to it representing its capacity. Assuming a steady state condition, find a maximal flow from one given city to the other.””
- First, cuts identify bottlenecks: by the max-flow min-cut theorem, the maximum flow from a source to a sink equals the capacity of the minimum cut separating them, so a system's throughput is decided by its narrowest separating link-set, every other edge being slack relative to that bottleneck.
- Network Flow Models
- the max-flow min-cut theorem was proved by Ford and Fulkerson (1956) and independently by Elias, Feinstein, and Shannon (1956).
Supported in partVerified against the publisher's abstract
The readable abstract confirms this is Ford & Fulkerson's 1956 maximal-flow paper and states the flow problem it treats, but says nothing about the max-flow min-cut theorem or its foundational-duality status.
“The problem discussed in this paper was formulated by T. Harris as follows: “Consider a rail network connecting two cities by way of a number of intermediate cities, where each link of the network has a number assigned to it representing its capacity. Assuming a steady state condition, find a maximal flow from one given city to the other.””
- the max-flow min-cut theorem was proved by Ford and Fulkerson (1956) and independently by Elias, Feinstein, and Shannon (1956).
Mechanisms¶
- Max-Flow Analysis
- Read off the min-cut. When no augmenting path is left, the set of saturated links separating source from sink is the minimum cut, and by the max-flow-min-cut theorem its capacity equals the maximum flow.
This sourceShows that exhaustion of augmenting chains identifies a separating cut whose capacity equals the maximal flow.
- Read off the min-cut. When no augmenting path is left, the set of saturated links separating source from sink is the minimum cut, and by the max-flow-min-cut theorem its capacity equals the maximum flow.
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 2 of 3 citations: 2 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Was it audited? Yes. A second, independent pass read the citation against the article text and recorded a verdict.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:6d21408bc9a6 · see in the full table