Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
1972/04/01 by Jack Edmonds, Richard M. Karp · 2,526 citations
Engineering · Mathematics · #Center (category theory) #Citation #Computer science #Library science #Mathematics #Operations research #Optimization and Mathematical Programming #Optimization and Packing Problems #Research center #Vehicle Routing Optimization Methods
paper · doi:10.1145/321694.321699
published in Journal of the ACM 19(2), 248-264 (Association for Computing Machinery)
openalex publication_date 1972/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/03
Abstract
article Free Access Share on Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems Authors: Jack Edmonds Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, CanadaView Profile , Richard M. Karp College of Engineering, Operations Research Center, University of California, Berkeley, California College of Engineering, Operations Research Center, University of California, Berkeley, CaliforniaView Profile Authors Info & Claims Journal of the ACMVolume 19Issue 2April 1972 pp 248–26410.1145/321694.321699Published:01 April 1972Publication History 1,682citation6,930DownloadsMetricsTotal Citations1,682Total Downloads6,930Last 12 Months607Last 6 weeks140 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
Citations
Cited by
- MAT-parameterization: Volumetric multi-patch parameterizations of complex domains for isogeometric analysis using MAT-based decomposition
- Efficient Uniform Negative Edge Weights
- Heuristic to reduce the complexity of complete bipartite graphs to accelerate the search for maximum weighted matchings with small error
- Algorithms and Complexity for Variants of Covariates Fine Balance
- The Cut and Dominating Set Problem in A Steganographer Network
- Constrained Cuts, Flows, and Lattice-Linearity
- Which Coauthor Should I Nominate in My 99 ICLR Submissions? A Mathematical Analysis of the ICLR 2026 Reciprocal Reviewer Nomination Policy
- Minimizing the Number of Code Switching Operations in Fault-Tolerant Quantum Circuits
- Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs
- Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
- Minimum Cost Flows, MDPs, and ℓ1-Regression in Nearly Linear Time for Dense Instances
- METTEOR: Robust Multi-Traffic Topology Engineering for Commercial Data Center Networks
- Online Bipartite Matching with Amortized O(log2 n) Replacements
- Target Assignment in Robotic Networks: Distance Optimality Guarantees and Hierarchical Strategies
- Efficient Dynamic MaxFlow Computation on GPUs
- Scalable Maxflow Processing for Dynamic Graphs
- Optimal Allocations under Strongly Pigou-Dalton Criteria: Hidden Layer Structure & Efficient Combinatorial Approach
- A practical Single Source Shortest Path algorithm for random directed graphs with arbitrary weight in expecting linear time
- A fast parallel algorithm for minimum-cost small integral flows
- Editing to a Connected Graph of Given Degrees
- On a Generalization of the Marriage Problem
- Graph-Theoretic Partitioning of RNAs and Classification of Pseudoknots-II
- Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
- Charting the Design Space of Neural Graph Representations for Subgraph Matching
- Source-Coded Online Algorithm for Multicast Subgraph Construction
- Popular conjectures imply strong lower bounds for dynamic problems
- Teacher transfers: equalizing deficits across schools
- Computing Optimal Trajectories for Optimal Transport in Nonuniform Environments
- Distributed clustering in partially overlapping feature spaces
- GeoBS: Information-Theoretic Quantification of Geographic Bias in AI Models
- Further Results on Rendering Geometric Intersection Graphs Sparse by Dispersion
- Parametrised Algorithms for Directed Modular Width
- Finite dominating sets for the refueling station location problem in fleet operations
- Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives
- A strongly polynomial algorithm for generalized flow maximization
- UNO: Unifying One-stage Video Scene Graph Generation via Object-Centric Visual Representation Learning
- Seeded graph matching for correlated Erdős-Rényi graphs
- NeuralQAAD: An Efficient Differentiable Framework for High Resolution Point Cloud Compression
- A spiking neural algorithm for the Network Flow problem
- Belief Propagation for Min-cost Network Flow: Convergence and Correctness
- Tightness of LP via Max-product Belief Propagation
- Harnessing Adaptive Topology Representations for Zero-Shot Graph Question Answering
- A Refutation of Elmasry's O(m √(n))-Time Algorithm for Single-Source Shortest Paths
- Counterfactual Reciprocal Recommender Systems for User-to-User Matching
- Security Games in Network Flow Problems
- PUMPS: Skeleton-Agnostic Point-based Universal Motion Pre-Training for Synthesis in Human Motion Tasks
- A Graph Theoretic Additive Approximation of Optimal Transport
- Fractional triangle decompositions in graphs with large minimum degree
- Scaling algorithms for approximate and exact maximum weight matching
- COUDER: Robust Topology Engineering for Optical Circuit Switched Data Center Networks
- Complexity of vehicle routing and scheduling problems
- A survey on exact algorithms for the maximum flow and minimum‐cost flow problems
- A Branch-and-Cut Algorithm for the Optimal Design of Parking Lots with One-way and Two-way Lanes
- Min-Cost Flow Duality in Planar Networks
- Some Network Optimization Models under Diverse Uncertain Environments
- Algebraic Algorithms for b-Matching, Shortest Undirected Paths, and f-Factors
- Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in O(n1.5 log n) Time
- Streaming, Distributed Variational Inference for Bayesian Nonparametrics
- Is Private Learning Possible with Instance Encoding?
- Lower Bounds on Cross-Entropy Loss in the Presence of Test-time Adversaries
- Efficient Resource Allocation under Adversary Attacks: A Decomposition-Based Approach
- Near approximation of maximum weight matching through efficient weight reduction
- Measuring Similarity of Graphs and their Nodes by Neighbor Matching
- Reviews: Topological Distances and Losses for Brain Networks
- On Simplex Pivoting Rules and Complexity Theory
- Belief propagation : an asymptotically optimal algorithm for the random assignment problem
- Flows in Almost Linear Time via Adaptive Preconditioning
- Lancet2: Improved and accelerated somatic variant calling with joint multi-sample local assembly graphs
- Distributed Adaptive Reinforcement Learning: A Method for Optimal Routing
- Capacities of repeater-assisted quantum communications
- Hierarchical Forecast Reconciliation on Networks: A Network Flow Optimization Formulation
- Reducing Energy Bloat in Large Model Training
- The quest for the GRAph Level autoEncoder (GRALE)
- Lagrangian Relaxation Applied to Sparse Global Network Alignment
- Geometric Combinatorics of Transportation Polytopes and the Behavior of the Simplex Method
- BROUTE: a benchmark suite for the implementation of standard vehicle routing algorithms
- Revisiting the Auction Algorithm for Weighted Bipartite Perfect Matchings
- Partial-Matching and Hausdorff RMS Distance Under Translation: Combinatorics and Algorithms
- 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
- Helix: Holistic Optimization for Accelerating Iterative Machine Learning
- Recent Advances in Fully Dynamic Graph Algorithms
- Network Flow Methods for the Minimum Covariates Imbalance Problem
- Improved algorithms for computing fisher's market clearing prices
- A Polynomial Time Algorithm for Fair Resource Allocation in Resource Exchange
- Max flows in O(nm) time, or better
- Managing contamination delay to improve Timing Speculation architectures
- An application of simultaneous diophantine approximation in combinatorial optimization
- A new algorithm for the directed chinese postman problem
- On Making Directed Graphs Eulerian
- Submodularity in Input Node Selection for Networked Systems
- Dinitz’ Algorithm: The Original Version and Even’s Version
- Faster scaling algorithms for general graph matching problems
- The NP-completeness column: An ongoing guide
- Lean 4 Machine-Verified Proof of P = NP via the Pedigree Polytope Membership Problem
- Fibonacci heaps and their uses in improved network optimization algorithms
- There’s plenty of room at the Top: What will drive computer performance after Moore’s law?
- The Nature of Computation
- Transfinite Ford–Fulkerson on a finite network
- Secret Key Generation for a Pairwise Independent Network Model
- Unit disk graphs
- Bottleneck flows in networks
- A new approach to the maximum-flow problem
- Beyond the flow decomposition barrier
- Estimating Flow Rates through Fracture Networks using Combinatorial Optimization
- Converting Linear Programs to Network Problems
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- Scaling and related techniques for geometry problems
- A data structure for dynamic trees
- From Hall's Marriage Theorem to Boolean Satisfiability and Back
- Secure Network Coding over Small Fields
- Dynamical optimal transport on discrete surfaces
- Hierarchical Maximum-Margin Clustering
- Robust Routing in Interdependent Networks
- Binary Classification from Multiple Unlabeled Datasets via Surrogate Set Classification
- Network Flow and Testing Graph Connectivity
- clusttraj: A Solvent-Informed Clustering Tool for Molecular Modeling
- Belief Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
- One-loop diagrams in the random Euclidean matching problem
- Finite-size corrections in the random assignment problem
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Maximum skew-symmetric flows and matchings
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
- A new—old algorithm for minimum‐cut and maximum‐flow in closure graphs
- Optimum Communication Spanning Trees
- Algorithms for two bottleneck optimization problems
- A note on practical construction of maximum bandwidth paths
- Unrooted unordered homeomorphic subtree alignment of RNA trees. [europepmc]
- A flood-based information flow analysis and network minimization method for gene regulatory networks. [europepmc]
- Novel genetic matching methods for handling population stratification in genome-wide association studies. [europepmc]
- Automated Planar Tracking the Waving Bodies of Multiple Zebrafish Swimming in Shallow Water. [europepmc]
- Minimum steering node set of complex networks and its applications to biomolecular networks. [europepmc]
- Achieving Crossed Strong Barrier Coverage in Wireless Sensor Network. [europepmc]
- Cutting Materials in Half: A Graph Theory Approach for Generating Crystal Surfaces and Its Prediction of 2D Zeolites. [europepmc]
- Bayesian nonparametric discovery of isoforms and individual specific quantification. [europepmc]
- A Two-Layer, Energy-Efficient Approach for Joint Power Control and Uplink-Downlink Channel Allocation in D2D Communication. [europepmc]
- 3D reconstruction identifies loci linked to variation in angle of individual sorghum leaves. [europepmc]
- Bed-Exit Behavior Recognition for Real-Time Images within Limited Range. [europepmc]
- Computing the sequence of k -cardinality assignments. [europepmc]
- Computing a maximum clique in geometric superclasses of disk graphs. [europepmc]
- Molecular dynamics identifies semi-rigid domains in the PD-1 checkpoint receptor bound to its natural ligand PD-L1. [europepmc]
- Communication and Computing Task Allocation for Energy-Efficient Fog Networks. [europepmc]
- Topological data analysis of human brain networks through order statistics. [europepmc]
- Matchtigs: minimum plain text representation of k-mer sets. [europepmc]
- Flows of Substances in Networks and Network Channels: Selected Results and Applications. [europepmc]
- Probabilistic computing with NbO x metal-insulator transition-based self-oscillatory pbit. [europepmc]
- Accurate integration of single-cell DNA and RNA for analyzing intratumor heterogeneity using MaCroDNA. [europepmc]
- Electric vehicle battery chemistry affects supply chain disruption vulnerabilities. [europepmc]
- Automated recognition of chromosome fusion using an alignment-free natural vector method. [europepmc]
- Topological state-space estimation of functional human brain networks. [europepmc]
- A model-free and distribution-free multi-omics integration approach for detecting novel lung adenocarcinoma genes. [europepmc]
- Coverage bias in small molecule machine learning. [europepmc]
Related