Maximal Flow Through a Network
1956/01/01 by L. R. Ford, D. R. Fulkerson · 2,348 citations
Mathematics · Social Sciences · #Algorithm #Combinatorics #Flow (mathematics) #Flow network #Geometry #Mathematical economics #Mathematical optimization #Mathematics #Maximum flow problem #State (computer science) #Topology (electrical circuits) #Transportation Planning and Optimization
paper · pdf · doi:10.4153/cjm-1956-045-5
published in Canadian Journal of Mathematics 8, 399-404 (Cambridge University Press)
openalex publication_date 1956/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
Abstract
Introduction. The problem discussed in this paper was formulated by T. Harris as follows: “Consider a rail network connecting two cities by way of a number of intermediate cities, where each link of the network has a number assigned to it representing its capacity. Assuming a steady state condition, find a maximal flow from one given city to the other.”
Cited by
- Causality and Minimal Supports in Recursive Datalog
- On the CGGRT Criterion for Detecting Bipartite Perfect Matchings in NC
- SHIRO: Near-Optimal Communication Strategies for Distributed Sparse Matrix Multiplication
- Sink Proximity: A Novel Approach for Online Vehicle Dispatch in Ride-hailing
- Constrained Cuts, Flows, and Lattice-Linearity
- Flow-Based Path Planning for Multiple Homogenous UAVs for Outdoor Formation-Flying
- Optimal Sequential Flows
- A Graph-theoretic perspective on centrality
- Set System Approximation for Binary Integer Programs: Reformulations and Applications
- Harmonic functions on Tutte embeddings and linearized Monge-Ampère equation
- Efficient Dynamic MaxFlow Computation on GPUs
- Scalable Maxflow Processing for Dynamic Graphs
- Source-Coded Online Algorithm for Multicast Subgraph Construction
- Minimum s--t Cuts with Fewer Cut Queries
- Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
- Geometric Control Theory Over Networks: Minimal Node Cardinality Disturbance Decoupling Problems
- Critical States Identiffcation in Power System via Lattice Partition and Its Application in Reliability Assessment
- A horizon tour of box-total dual integrality
- FedAVOT: Exact Distribution Alignment in Federated Learning via Masked Optimal Transport
- H2EAL: Hybrid-Bonding Architecture with Hybrid Sparse Attention for Efficient Long-Context LLM Inference
- A (4/3+ε)-Approximation for Preemptive Scheduling with Batch Setup Times
- Total unimodularity: Adding a row or a column to the incidence matrix of a directed graph
- Harnessing Adaptive Topology Representations for Zero-Shot Graph Question Answering
- Subquadratic Approximation Algorithms for Separating Two Points with Objects in the Plane
- Fixed-Point-Oriented Programming: A Concise and Elegant Paradigm
- Aligning gene trees with family trees
- A survey on exact algorithms for the maximum flow and minimum‐cost flow problems
- Simplifications and speedups of the pseudoflow algorithm
- Improved Lower Bounds on Multiflow-Multicut Gaps
- The Capacity Constraint Physarum Solver
- Connected k-Median with Disjoint and Non-disjoint Clusters
- Faster Algorithm for Second (s,t)-mincut and Breaking Quadratic barrier for Dual Edge Sensitivity for (s,t)-mincut
- Minimizing Communication for Parallel Symmetric Tensor Times Same Vector Computation
- Message recovery attack in NTRU through VFK lattices
- A novel stratified sampler with unbalanced refinement for network reliability assessment
- Hierarchical Forecast Reconciliation on Networks: A Network Flow Optimization Formulation
- Unsplittable Multicommodity Flows in Outerplanar Graphs
- Community detection in graphs
- Minimal Lp-congestion spanning trees on weighted graphs
- DHMS: A Digital Hostel Management System Integrating Campus ChatBot, Predictive Intelligence, and Real-Time Automation
- Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
- Max flows in O(nm) time, or better
- A Mathematical Theory of Payment Channel Networks
- The Nature of Computation
- The SECOQC Quantum-Key-Distribution Network in Vienna
- Transfinite Ford–Fulkerson on a finite network
- Graph Theoretical Analysis Reveals: Women’s Brains Are Better Connected than Men’s
- A new approach to the maximum-flow problem
- Beyond the flow decomposition barrier
- Kernelization: Theory of Parameterized Preprocessing
- Line graphs, link partitions, and overlapping communities
- Maximum-Minimum Sätze über Graphen
- Clique graphs and overlapping communities
- Tools for quantum network design
- On the graph structure of convex polyhedra in n -space
- The DoF of Two-Way Butterfly Networks
- AT-Approach to Some Results on Cuts and Metrics
- Aggregating quantum repeaters for the quantum internet
- Quantum Max-flow/Min-cut
- Exact ground-state properties of disordered Ising systems
- Robust logarithmic lower bound on shared-resource cost for f-routing
- Totally equimodular matrices: decomposition and triangulation
- The ellipsoid method and its consequences in combinatorial optimization
- Ford–Fulkerson algorithm [wikipedia]
- Maximum flow problem [wikipedia]
- Graph Theoretical Analysis Reveals: Women's Brains Are Better Connected than Men's. [europepmc]
- BRANE Cut: biologically-related a priori network enhancement with graph cuts for gene regulatory network inference. [europepmc]
- A plausible neural circuit for decision making and its formation based on reinforcement learning. [europepmc]
- Cutting Materials in Half: A Graph Theory Approach for Generating Crystal Surfaces and Its Prediction of 2D Zeolites. [europepmc]
- Systems biology approach reveals a link between mTORC1 and G2/M DNA damage checkpoint recovery. [europepmc]
- Evaluation of segmentation algorithms for optical coherence tomography images of ovarian tissue. [europepmc]
- Disease Pathway Cut for Multi-Target drugs. [europepmc]
- Hydraulically informed graph theoretic measure of link criticality for the resilience analysis of water distribution networks. [europepmc]
- Digitizable therapeutics for decentralized mitigation of global pandemics. [europepmc]
- Assessing recall of personal sun exposure by integrating UV dosimeter and self-reported data with a network flow framework. [europepmc]
- Functional Transcription Factor Target Networks Illuminate Control of Epithelial Remodelling. [europepmc]
- Operads for complex system design specification, analysis and synthesis. [europepmc]
- An open source computational workflow for the discovery of autocatalytic networks in abiotic reactions. [europepmc]
- Earlier Bedtime and Effective Coping Skills Predict a Return to Low-Risk of Depression in Young Adults during the COVID-19 Pandemic. [europepmc]
- Multiple genome alignment in the telomere-to-telomere assembly era. [europepmc]
- Mathematical measures of societal polarisation. [europepmc]
- DeepPatent2: A Large-Scale Benchmarking Corpus for Technical Drawing Understanding. [europepmc]
- Enhanced forest fire evacuation planning using real-time sensor and GPS algorithm. [europepmc]
- LASP to the Future of Atomic Simulation: Intelligence and Automation. [europepmc]
- An Accelerated Maximum Flow Algorithm with Prediction Enhancement in Dynamic LEO Networks. [europepmc]
- Class-balanced negative training sets for improving classifier model predictions of enhancer-promoter interactions. [europepmc]
- On the Parameterized Complexity of Eulerian Strong Component Arc Deletion. [europepmc]
- Segmentation and Multimodal Characterization of Metal Particles in the Human Hippocampus Using Discrete Segmentation Algorithms and Correlation Spectral Analysis. [europepmc]
- Smart emergency multi-attribute decision-making for typhoon response based on a hybrid intuitionistic fuzzy approach. [europepmc]
- How current perspectives on algorithmic thinking can be applied to students’ engagement in algorithmatizing tasks [europepmc]
Related