Maximal Flow Through a Network

1956/01/01 by L. R. Ford, D. R. Fulkerson · 32 citations
Social Sciences · #Transportation Planning and Optimization

paper · pdf · doi:10.4153/cjm-1956-045-5

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

Related

• Note about network decomposition by maximum flow
• Finding a Feasible Flow in a Strongly Connected Network
• Multi-Commodity Network Flows
• Yet another approach to the Maximum Flow
• Failure of classical traffic and transportation theory: The maximization of the network throughput maintaining free flow conditions in network