6 articles
Augmenting path
An augmenting path is a path along which a maximum flow or matching can be improved, in algorithms such as Ford-Fulkerson, Edmonds-Karp, and Hopcroft-Karp; finding none certifies optimality.
Blocking flow
A blocking flow is a flow in a network that saturates at least one arc on every source-to-sink path, so no admissible path remains usable.
Flow network
A flow network is a directed graph in which each edge has a capacity, with a source that generates flow and a sink that absorbs it; the central problem is finding a maximum flow.
Ford–Fulkerson algorithm
The Ford–Fulkerson algorithm, also called the Ford–Fulkerson method, computes maximum flow in a network by repeatedly augmenting along paths; it was proposed in 1956 by Ford and Fulkerson.
Max-flow min-cut theorem
The max-flow min-cut theorem states that the maximum flow from source to sink in a network equals the minimum cut capacity, proved by Ford and Fulkerson in 1956.
Push–relabel maximum flow algorithm
The push–relabel maximum flow algorithm, also known as the push–relabel algorithm or preflow push, is a maximum flow algorithm introduced by Goldberg and Tarjan in 1988.