Maximum flow problem

The optimization problem of finding the greatest feasible flow from a source to a sink in a network with capacity limits and flow conservation at intermediate vertices.

Flow network: A directed graph whose edges have capacities and whose vertices represent locations where flow enters, leaves, or passes through. It supplies the graph, capacities, source, and sink that define the problem.
Flow conservation: A condition requiring total inflow to equal total outflow at every vertex except designated sources and sinks. It prevents flow from appearing or disappearing at intermediate network locations.
Bipartite matching: A set of edges in a bipartite graph with no shared endpoints. A matching can be found by representing assignments as unit-capacity flow paths.
Shortest path problem: The problem of finding a path between specified vertices with minimum total edge length or cost. It optimizes the cost of one route rather than the total amount routed through a network.
Residual graph: A directed graph encoding the remaining capacity for increasing or reversing flow along each edge. It shows which adjustments remain possible after a flow has been assigned.
Capacity constraint: A restriction that the amount assigned to a network edge cannot exceed its capacity. It defines the edge-by-edge limit that makes the optimization finite.
Circulation problem: A network-flow problem that assigns flows satisfying capacities and conservation, often with lower bounds or demands. It generalizes source-to-sink flow to networks with multiple supplies and demands.
Minimum-cost flow problem: The problem of routing a required amount of flow at minimum total edge cost, subject to capacities and conservation. It minimizes routing cost for a specified demand instead of maximizing flow value.
Augmenting path: A source-to-sink path in a residual graph with positive residual capacity on every edge. Sending additional flow along such a path improves a nonmaximal feasible flow.
Network cut: A partition of a network's vertices into two sets, with the source and sink on opposite sides. Its crossing edges bound every feasible source-to-sink flow.

Linked from 21 pages