Publication record · 18.cifr/1956.ford.max-flow

Maximal Flow Through a Network

v1.0.0

L. R. Ford (RAND Corporation), D. R. Fulkerson (RAND Corporation)

RAI18.cifr/1956.ford.max-flow

Canadian Journal of Mathematics· 1956· doi:10.4153/CJM-1956-045-5

Introduction. 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.

network flowmax-flow min-cutcombinatorial optimizationgraph algorithmscapacitated networks

✦ Research context

What this agent contributes to the literature.

Problem solved

Rail and logistics planners had no systematic method to compute maximum network throughput between two terminals, posed as a military logistics problem by T. Harris at RAND. This paper provides both a tight theoretical bound and a practical algorithm with an optimality certificate.

Novelty

Ford and Fulkerson proved the max-flow min-cut theorem: the maximum flow from source to sink equals the minimum capacity of any cut separating them. They gave the first constructive augmenting-path algorithm to achieve this bound, establishing a foundational duality result in combinatorial optimization.

Related research

Computing related research...

Canvas contract1-in / 1-out · unpacked into network, params legacy ports

Sample data

Loading sample data...

Total calls

This month

Citations

Last called

—

Image digest

sha256:2d7313d12f89323342e14d3f944ba73b0c7c1272bfffc6890cc9c92939f19d35

Invoke command

python main.py

Inputs

input:application/json

Outputs

output:application/json

Citation

Loading DOI…

Invoke

CPU compute only

How to get GPU access: Your university, lab, or company can become a CIFR institutional member. Members get GPU-accelerated runs for all their researchers. Contact us

Pre-filled with the paper's canonical scenario. Click Invoke agent to reproduce the original result, or edit the JSON below to run a counterfactual.

inputapplication/jsonoptional

Unified canvas input containing network topology and flow parameters

Leave empty to run the paper's canonical scenario.

Recent invocations(0)

No invocations yet — be the first to call this agent.