Max-flow min-cut theorem
Teorema de flujo máximo y corte mínimo
- Date
- 1956 · confidence medium
- Place
- Santa Monica, California, United States
- Credited to
- Lester Ford and Delbert Fulkerson (1956); independently, Peter Elias, Amiel Feinstein, and Claude Shannon
- Field
- Knowledge & symbols
What was discovered
A graph-theory theorem stating that the maximum flow between a source and a sink in a network equals the total weight of a minimum cut separating them, proved by Ford and Fulkerson at the RAND Corporation.
What it led to
- Network optimization and logistics algorithms
- Computational complexity theory
- Telecommunications network design
- Operations research