Maximum flow problem
Problem of maximizing flow through a network from source to sink.
The maximum flow problem is a fundamental concept in optimization theory, concerned with finding the feasible flow through a flow network that achieves the highest possible flow rate from a source to a sink. E. Harris and F. S. Ross as a simplified model of Soviet railway traffic flow, and the max-flow min-cut theorem states that the maximum value of an s-t flow equals the minimum capacity of an s-t cut.
- field
- Optimization theory, network flow
- known_for
- Maximum flow problem, max-flow min-cut theorem
Lore & Background
E. Harris and F. S. Ross as a simplified model of Soviet railway traffic flow. Ford, Jr. and Delbert R. Fulkerson created the first known algorithm, the Ford–Fulkerson algorithm. E. Harris, who, with General F. S. Ross (Ret.), had formulated a simplified model of railway traffic flow and pinpointed this problem as central.
Reader's Guide
The maximum flow problem is a cornerstone of network flow theory, with the max-flow min-cut theorem providing a deep duality between flow and cut capacities. Over the years, improved solutions emerged, including the shortest augmenting path algorithm of Edmonds and Karp and independently Dinitz; the blocking flow algorithm of Dinitz; the push-relabel algorithm of Goldberg and Tarjan; and the binary blocking flow algorithm of Goldberg and Rao. Algorithms by Sherman and Kelner, Lee, Orecchia and Sidford find approximately optimal maximum flow but only work in undirected graphs. Orlin published an O(|V||E|) algorithm.
Did You Know?
- The max-flow min-cut theorem states that the maximum value of an s-t flow equals the minimum capacity of an s-t cut.
Frequently Asked Questions
What are Maximum flow problem's powers/role?
Its core ability is to determine the highest possible flow rate that can be routed through a directed graph from source to sink while respecting every edge's capacity constraint. In practice, it underpins everything from internet routing to airline scheduling and bipartite matching.
How does Maximum flow problem's story end?
Every episode resolves with the max-flow min-cut theorem, which guarantees that the largest achievable s-t flow is exactly equal to the smallest capacity s-t cut in the network. This duality means you can certify optimality simply by identifying that bottleneck cut.
More in Algorithms And Data Structures 25-38
Elsewhere in the Algorithms And Data Structures universe
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record