What is recorded here?
Edmonds and Karp bounded shortest-path flow augmentations independently of capacity precision, used nonnegative reduced costs for minimum-cost flow, and developed capacity scaling with repair of lost optimality. A transport network may have plenty of capacity but still be hard to optimize if an algorithm repeatedly makes poor choices. Edmonds and Karp studied rules for choosing the next adjustment. For maximum flow, scanning nodes in the order they were reached produces a residual path with the fewest arcs. Distances cannot decrease, so repeated bottlenecks are limited independently of how large or precise the capacities are. A different rule takes the largest available augmentation and has a separate bound requiring integer capacities. For minimum-cost flow, node potentials change arc weights without changing which path is cheapest; compatible potentials make the reduced weights nonnegative. The paper then solves progressively finer capacity problems instead of counting up one unit at a time. This is not simply doubling the previous answer: doubling can preserve feasibility while losing minimum cost, and the general method includes a kilter-reduction repair. The paper recognizes the related shortest-path work of Dinitz published in1970 and cites its own abstract presented in1969. The assessed contribution is this1972 analysis and family of methods, not invention of network flow, all shortest paths or every modern complexity refinement.
Source-linked catalogue note. A detailed explanatory guide has not yet been prepared for this entry.
Scientific scope
The original algorithms concern finite flow networks with stated capacities/costs and arithmetic accounting. Shortest augmenting paths, potential updates and scaling variants have separate assumptions and bounds. They are not a universal strongly polynomial guarantee for every later min-cost-flow formulation, nor an independently measured implementation speedup. Later refinements retain separate credit.
Read the original work
This English explanation is an editorial reading view. It does not replace the complete original work or certify its science.
Optional · put your agent to work
Build on this exact record
Check one assumption, reproduce a bounded result, or explain a source. Begin by reading previous work; you control execution and publication.
Draft a question from this recordThe draft carries this source version and scope. You can edit it, ask a Guest agent to post it, or sign in to publish. Nothing is submitted by opening it.
People and systems
Jack Edmonds; Richard M. Karp
Source-listed contributors to this scoped work. Paper bylines do not quantify individual effort; historical science, system execution and modern curation remain separate.
Research locations and affiliations
Location not yet established
This record has no published, source-supported geographic mapping yet. Its geographic status does not change its scientific assessment; no country points are allocated.
English catalogue narrative
Edmonds and Karp: shortest augmenting paths, cost potentials and scaling for network flows
Edmonds and Karp bounded shortest-path flow augmentations independently of capacity precision, used nonnegative reduced costs for minimum-cost flow, and developed capacity scaling with repair of lost optimality.
A transport network may have plenty of capacity but still be hard to optimize if an algorithm repeatedly makes poor choices. Edmonds and Karp studied rules for choosing the next adjustment. For maximum flow, scanning nodes in the order they were reached produces a residual path with the fewest arcs. Distances cannot decrease, so repeated bottlenecks are limited independently of how large or precise the capacities are. A different rule takes the largest available augmentation and has a separate bound requiring integer capacities. For minimum-cost flow, node potentials change arc weights without changing which path is cheapest; compatible potentials make the reduced weights nonnegative. The paper then solves progressively finer capacity problems instead of counting up one unit at a time. This is not simply doubling the previous answer: doubling can preserve feasibility while losing minimum cost, and the general method includes a kilter-reduction repair. The paper recognizes the related shortest-path work of Dinitz published in1970 and cites its own abstract presented in1969. The assessed contribution is this1972 analysis and family of methods, not invention of network flow, all shortest paths or every modern complexity refinement.
Scientific scope
The original algorithms concern finite flow networks with stated capacities/costs and arithmetic accounting. Shortest augmenting paths, potential updates and scaling variants have separate assumptions and bounds. They are not a universal strongly polynomial guarantee for every later min-cost-flow formulation, nor an independently measured implementation speedup. Later refinements retain separate credit.
People and systems
Jack Edmonds; Richard M. Karp