The maximum flow problem is a classic optimization problem in network flow theory, which aims to find the maximum flow that can be sent from a source node (often referred to as the "source") to a sink node (often referred to as the "sink" or "target") in a flow network. A flow network is a directed graph where each edge has a capacity representing the maximum allowable flow that can pass through that edge.
Articles by others on the same topic
The maximum flow problem maximises the strength of a flow from a source to a sink subject to flow conservation and flow network edge capacities. The max-flow min-cut theorem identifies the optimum with the least capacity of a cut of a flow network. A feasible flow and a cut of a flow network of equal value certify optimality without requiring a particular choice of augmenting paths.