Maximal Flow Through a Network

DOI10.4153/CJM-1956-045-5zbMath0073.40203OpenAlexW4213060883WikidataQ55880658 ScholiaQ55880658MaRDI QIDQ3237973

D. R. Fulkerson, L. R. Ford, Jr.

Publication date: 1956

Published in: Canadian Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4153/cjm-1956-045-5

zbMATH Keywords

Topology

Related Items

Minimum Cuts in Surface Graphs, Zur Berechnung der Verteilung graphentheoretischer Zufallsvariablen, BIRNBAUM CRITICALITY AND IMPORTANCE MEASURES FOR MULTISTATE SYSTEMS WITH REPAIRABLE COMPONENTS, Recent developments in maximum flow algorithms, An Algorithm for Vertex-pair Connectivity, Logical s-t Min-Cut Problem: An Extension to the Classic s-t Min-Cut Problem, On Fault-Tolerant Low-Diameter Clusters in Graphs, Optimization in telecommunication networks, APPROXIMATION ALGORITHMS FOR FLEXIBLE JOB SHOP PROBLEMS, GEOMETRIC ALGORITHMS FOR STATIC LEAF SEQUENCING PROBLEMS IN RADIATION THERAPY, Unnamed Item, Simplifications and speedups of the pseudoflow algorithm, Exact and Approximation Algorithms for the Expanding Search Problem, Graph Bisection with Pareto Optimization, Optimal interdiction of a supply network, TBGMax: leveraging two-boundary graph pattern for lossless maximum-flow acceleration, Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems, Cores and related solution concepts for multi-choice games, Persuasion and dynamic communication, Generalized max flows and augmenting paths, Computing Area-Optimal Simple Polygonizations, How vulnerable is an undirected planar graph with respect to max flow, Matching cells, FlowLoc problems with maximum excess flow, On the bond polytope, A fast maximum flow algorithm, Paths and flows for centrality measures in networks, Graph fragmentation problem: analysis and synthesis, MTGL-ADMET: a novel multi-task graph learning framework for ADMET prediction enhanced by status-theory and maximum flow, Decomposition of probability marginals for security games in abstract networks, Applications and efficient algorithms for integer programming problems on monotone constraints, Two‐stage stochastic minimum s − t cut problems: Formulations, complexity and decomposition algorithms, An augmenting‐flow algorithm for a class of node‐capacitated maximum flow problems, Discrete bulk reconstruction, Foundations of operations research: from linear programming to data envelopment analysis, Unnamed Item, Unnamed Item, Making Bipartite Graphs DM-Irreducible, The st-bond polytope on series-parallel graphs, Unnamed Item, Unnamed Item, The Maximum Flow Problem for Oriented Flows, Optimizing Traffic Signal Timings for Mega Events., Edge-Cuts of Optimal Average Weights, Unnamed Item, A self-stabilizing algorithm for the maximum flow problem, Rapidly Solving an Online Sequence of Maximum Flow Problems with Extensions to Computing Robust Minimum Cuts, A Flexible, Natural Formulation for the Network Design Problem with Vulnerability Constraints, Practical Minimum Cut Algorithms, Converse bounds for quantum and private communication over Holevo–Werner channels, Multiway cuts in directed and node weighted graphs, Mincut Sensitivity Data Structures for the Insertion of an Edge, Reverse maximum flow problem under the weighted Chebyshev distance, Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs., Complexity and compilability of diagnosis and recovery of graph-based systems, The Complexity of Finding Small Separators in Temporal Graphs, The computational complexity of optimal blocking of vertices in the digraph, A submodular optimization problem with side constraints, Expanders Are Universal for the Class of All Spanning Trees, Group field theory and holographic tensor networks: dynamical corrections to the Ryu–Takayanagi formula, Über reguläre Kettengruppen, A fuzzy max-flow min-cut theorem., Fast augmentation algorithms for maximising the output flow in repairable flow networks after edge failures, Limsup deviations on trees, Sparse Process Flexibility Designs: Is the Long Chain Really Optimal?, A cycle augmentation algorithm for minimum cost multicommodity flows on a ring, Time-varying universal maximum flow problems, Shortest-Path-Finder Algorithm in a Two-Dimensional Array of Nonlinear Electronic Circuits, A strongly polynomial time algorithm for a constrained submodular optimization problem, Improved availability bounds for binary and multistate monotone systems with independent component processes, Homomorphisms of Cayley graphs and cycle double covers, Extension of Rescheduling Based on Minimal Graph Cut, A Parametrized Analysis of Algorithms on Hierarchical Graphs, Unnamed Item, Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm, The multiroute maximum flow problem revisited, Approximating small balanced vertex separators in almost linear time, Systems of representatives, Opposite Elements in Clutters, BRIDGE LANE DIRECTION SPECIFICATION FOR SUSTAINABLE TRAFFIC MANAGEMENT, On Mergings in Acyclic Directed Graphs, Unnamed Item, Faster algorithms for shortest path and network flow based on graph decomposition, Polyhedral Results and Branch-and-Cut for the Resource Loading Problem, Flows with Unit Path Capacities and Related Packing and Covering Problems, Improved queue-size scaling for input-queued switches via graph factorization, Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs, Fast Augmenting Paths by Random Sampling from Residual Graphs, Unnamed Item, Combinatorial Optimization: The Interplay of Graph Theory, Linear and Integer Programming Illustrated on Network Flow, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Explainable dynamic programming, Analysis of Biological Data by Graph Theory Approach Searching of Iron in Biological Cells, The connectivity function of a graph, Evacuation schemes on Cayley graphs and non-amenability of groups, Network Flow-Based Refinement for Multilevel Hypergraph Partitioning, Chordless paths through three vertices, Minimax problem of suppressing a communication network, Polyhedral proof methods in combinatorial optimization, A decomposition algorithm for multi-terminal network flows, A simple linear algorithm for the edge-disjoint \((s, t)\)-paths problem in undirected planar graphs, Single-commodity robust network design with finite and hose demand sets, Truthful mechanism design for multidimensional scheduling via cycle monotonicity, Parameterized complexity dichotomy for \textsc{Steiner Multicut}, Generalized network measures based on modulus of families of walks, Quick max-flow algorithm, On the hardness of bribery variants in voting with CP-nets, The data transfer problem in a system of systems, Approximation algorithms for requirement cut on graphs, Improved max-flow min-cut algorithms in a circular disk failure model with application to a road network, Stronger multi-commodity flow formulations of the (capacitated) sequential ordering problem, Network interdiction via a critical disruption path: branch-and-price algorithms, Polyhedral results on single node variable upper-bound flow models with allowed configurations, Topology optimisation of repairable flow networks for a maximum average availability, Three commodity flows in graphs, Towards duality of multicommodity multiroute cuts and flows: multilevel ball-growing, The extremal length of a network, The multi-multiway cut problem, Combinatorial and geometric properties of the max-cut and min-cut problems, Weighted maximum-clique transversal sets of graphs, Simplifying maximum flow computations: the effect of shrinking and good initial flows, A linear time algorithm for the induced disjoint paths problem in planar graphs, An \(O(EV\log^2V)\) algorithm for the maximal flow problem, f-factors and related decompositions of graphs, DNA sequence assembly involving an acyclic graph model, The maximum flow problem of uncertain network, A capable neural network model for solving the maximum flow problem, Properties of the DGS-auction algorithm, On the theoretical efficiency of various network flow algorithms, Galois geometries and coding theory, Multicommodity flows in planar graphs, Partitioning planar graphs: a fast combinatorial approach for max-cut, Energy-efficient paths in radio networks, Error exponents for two-hop Gaussian multiple source-destination relay channels, Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs, A survey of dynamic network flows, On maximum flows in polyhedral domains, Nuclear threat detection with mobile distributed sensor networks, Optimal cocircuits in regular matroids and applications, Paths of bounded length and their cuts: parameterized complexity and algorithms, Graph clustering, An efficient algorithm for the minimum capacity cut problem, Exact and approximate resolution of integral multiflow and multicut problems: Algorithms and complexity, Counting and sampling minimum cuts in genus \(g\) graphs, Hall's theorem and extending partial Latinized rectangles, Orthogonal graph drawing with flexibility constraints, Selecting a discrete portfolio, Modeling profit sharing in combinatorial exchanges by network flows, A singular radial connection over \(\mathbb B^5\) minimizing the Yang-Mills energy, About the minimum mean cycle-canceling algorithm, A new approach for solving the network problems, The problem of maximum flow with minimum attainable cost in a network, Riemann-Roch theory for graph orientations, Graph cuts with interacting edge weights: examples, approximations, and algorithms, The asymptotics of quantum max-flow min-cut, Bit threads and holographic entanglement, A polynomial-time simplex method for the maximum \(k\)-flow problem, A novel node-based sequential implicit enumeration method for finding all \(d\)-MPs in a multistate flow network, Interval scheduling maximizing minimum coverage, A specialized network simplex algorithm for the constrained maximum flow problem, Disjoint paths in sparse graphs, Selected topics on assignment problems, Optimal cuts in graphs and statistical mechanics, Maximum bipartite flow in networks with adaptive channel width, Rapidly computing robust minimum capacity s-t cuts: a case study in solving a sequence of maximum flow problems, A note on two problems in connexion with graphs, Local ratio with negative weights., A new strategy for the undirected two-commodity maximum flow problem, The multi-terminal maximum-flow network-interdiction problem, Measuring agility of networked organizational structures via network entropy and mutual information, Network flow interdiction on planar graphs, Maximum flows and minimum cuts in the plane, The \(k\)-centrum shortest path problem, Executability of scenarios in Petri nets, An efficient minimum and maximum global snapshot algorithm, \((F, I)\)-security in graphs, A \((0,1)\)-matrix existence theorem and equivalent tiling problems with dimers and monomers, A node-capacitated Okamura-Seymour theorem, Computing monotone disjoint paths on polytopes, Random assignment under weak preferences, Capacitive flows on a 2D random net, A simple algorithm for multicuts in planar graphs with outer terminals, Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time, Scheduling multiprocessor UET tasks of two sizes, An approach to the parallel solution of a high-dimensional basic flow problem, Flows with unit path capacities and related packing and covering problems, Recent trends in combinatorial optimization, On a simple deadlock recovery problem, Fuzzy quantities in networks, Financial systems: A few theoretical and algebraic considerations for their modeling, A class of h-perfect graphs, New solutions for disjoint paths in P systems, Compact formulations of the Steiner traveling salesman problem and related problems, Efficient algorithms for estimating loss of information in a complex network: applications to intentional risk analysis, Backdoors to q-Horn, The nucleolus of balanced simple flow networks, Length-bounded cuts: proper interval graphs and structural parameters, Dynamic programming and graph optimization problems, Two-edge connected spanning subgraphs and polyhedra, Invulnerability of power grids based on maximum flow theory, Metric and ultrametric inequalities for directed graphs, SSE and SSD: page-efficient searchable symmetric encryption, A generalization of the scaling max-flow algorithm, From graph cuts to isoperimetric inequalities: convergence rates of Cheeger cuts on data clouds, Exact and approximation algorithms for sensor placement against DDoS attacks, An overview of graph covering and partitioning, Optimally balancing assembly lines with different workstations, Iteratively reweighted least squares and slime mold dynamics: connection and convergence, Ideal, non-extended formulations for disjunctive constraints admitting a network representation, An analytic symmetrization of max flow-min cut, Circuit duality for recurrent Markov processes, On solving mutual liability problems, The stochastic stability of decentralized matching on a graph, A polyhedron with all \(s-t\) cuts as vertices, and adjacency of cuts, Robust routing in deterministic delay-tolerant networks, On perfectly two-edge connected graphs, More on the rainbow disconnection in graphs, An auction algorithm for the max-flow problem, Rainbow disconnection in graphs, Estimating parameters of a probabilistic heterogeneous block model via the EM algorithm, The general counterfeit coin problem, Dynamic graph models, Mincut sensitivity data structures for the insertion of an edge, A fast algorithm for the minimax flow problem with 0/1 weights, Matching and scheduling of student-company-talks for a university it-speed dating event, Enhanced instance space analysis for the maximum flow problem, A decentralized flow redistribution algorithm for avoiding cascaded failures in complex networks, Some bounds on the generalised total chromatic number of degenerate graphs, Sparse certificates for 2-connectivity in directed graphs, A \(T_X\)-approach to some results on cuts and metrics, Multiterminal flows and cuts, Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time, Bit threads and holographic monogamy, On the fractionality of the path packing problem, Fuzzy optimal flow on imprecise structures, Optimal wavelength-routed multicasting, Strong converse theorems for multimessage networks with tight cut-set bound, A decomposition for the Schrödinger equation with applications to bilinear and multilinear estimates, Alternating signed bipartite graphs and difference-1 colourings, Intractability of min- and max-cut in streaming graphs, Simultaneous classification and community detection on heterogeneous network data, Controlling a random population, Topology design for on-demand dual-path routing in wireless networks, Graphs with no \(K_{3,3}\) minor containing a fixed edge, Maximum flow in a network with fuzzy arc capacities, The ellipsoid method and its consequences in combinatorial optimization, Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments, Structure on the top homology and related algorithms, Formalizing network flow algorithms: a refinement approach in Isabelle/HOL, On efficiently solvable cases of quantum \(k\)-SAT, Investments in stochastic maximum flow networks, Network flow with intermediate storage: models and algorithms, Ancestor tree for arbitrary multi-terminal cut functions, Allocation under a general substitution structure, Short proofs on multicommodity flows and cuts, A simplified algorithm computing all \(s-t\) bridges and articulation points, Market implementation of multiple-arrival multiple-deadline differentiated energy services, Maximum concurrent flows and minimum cuts, Implementing the Ford-Fulkerson labeling algorithm with fixed-order scanning, Greedy oriented flows, Parametric multiroute flow and its application to multilink-attack network, Matching theory -- a sampler: From Dénes König to the present, Disaggregated Benders decomposition and branch-and-cut for solving the budget-constrained dynamic uncapacitated facility location and network design problem, On matching numbers of tree and bipartite degree sequences, A faster polynomial algorithm for the constrained maximum flow problem, Network interdiction to minimize the maximum probability of evasion with synergy between applied resources, The complexity of finding small separators in temporal graphs, Trade-off for heterogeneous distributed storage systems between storage and repair cost, A hybrid heuristic for the maximum dispersion problem, Ein kombinatorischer Beweis des Satzes von R. L. Ford und D. R. Fulkerson, On the connectivity of clusters, On partitions of a partially ordered set, Box-total dual integrality, box-integrality, and equimodular matrices, Parameterized complexity of length-bounded cuts and multicuts, Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem, Margin of victory for tournament solutions, A new LP rounding algorithm for the active time problem, Computational investigations of maximum flow algorithms, Efficient algorithms for abstract flow with partial switching, Plant location with minimum inventory, Multicommodity flows in graphs, Negativity spectra in random tensor networks and holography, Colored cut games, The line index and minimum cut of weighted graphs, Maximin problem of communication network synthesis, An algorithmic study of the maximum flow problem: A comparative statistical analysis, A mechanized proof of the max-flow min-cut theorem for countable networks with applications to probability theory, Abstract network flow with intermediate storage for evacuation planning, A primal-dual approximation algorithm for the survivable network design problem in hypergraphs, Flow in planar graphs with vertex capacities, A dual description of the class of games with a population monotonic allocation scheme, Bounds for the rainbow disconnection numbers of graphs, On the \(l\)-connectivity of a digraph, Computing the effective crack energy of heterogeneous and anisotropic microstructures via anisotropic minimal surfaces, Firing partial orders in a Petri net, Safety in \(s\)-\(t\) paths, trails and walks, Solving simultaneous target assignment and path planning efficiently with time-independent execution, Minimum weight clustered dominating tree problem, Minimum separators and Menger's theorem, Some insights on dynamic maintenance of Gomory-Hu tree in cactus graphs and general graphs, A survey on exact algorithms for the maximum flow and minimum‐cost flow problems, Explicit Baranyai partitions for quadruples, Part I: Quadrupling constructions, The Cheeger cut and Cheeger problem in metric measure spaces, On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts, A survey of parameterized algorithms and the complexity of edge modification, How vulnerable is an undirected planar graph with respect to max flow, Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique, The resilience of conjunctive queries with inequalities, A new maximal flow algorithm for solving optimization problems with linguistic capacities and flows, Isolation scheduling on multicores: model and scheduling approaches, The project scheduling polyhedron: Dimension, facets and lifting theorems, OPTIMIZING DATA THROUGHPUT IN CLIENT/SERVER SYSTEMS BY KEEPING QUEUE SIZES BALANCED, Constrained flow control in storage networks: capacity maximization and balancing, Hamiltonicity and cycle extensions in 0-block-intersection graphs of balanced incomplete block designs, Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search, On swarm-level resource allocation in BitTorrent communities, Quantum Max-flow/Min-cut, Sensitivity analysis of 0-1 multiterminal network flows, Tight Bounds for Gomory-Hu-like Cut Counting, The Cost of Stability in Network Flow Games, Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation, On the dominant of the \(s\)-\(t\)-cut polytope: vertices, facets, and adjacency, Lehman's Theorem and the Directed Steiner Tree Problem, Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem, The optimal partitioning of networks, The maximum integer multiterminal flow problem in directed graphs, The Generalized Regenerator Location Problem, An $\mathcal{O}(\log {m})$-Competitive Algorithm for Online Machine Minimization, Extending SMT solvers with support for finite domain \texttt{alldifferent} constraint, Efficient continuous contraflow algorithms for evacuation planning problems, Efficient random graph matching via degree profiles, A theoretical and experimental study of a new algorithm for minimum cost flow in dynamic graphs, Social welfare in search games with asymmetric information, Reconciliation of a gene network and species tree, The Cheeger cut and Cheeger problem in metric graphs, Polyhedral Combinatorics in Combinatorial Optimization, Algorithms for non-linear and stochastic resource constrained shortest path, ON THE COMPLEXITY OF THE WHITEHEAD MINIMIZATION PROBLEM, Depletable channels: dynamics, behaviour, and efficiency in network design, Approximation algorithms for the generalized incremental knapsack problem, A ranking model for the greedy algorithm and discrete convexity, Maximum-Minimum Sätze über Graphen, The symbolic algorithms for maximum flow in networks, Polynomial-time algorithms for special cases of the maximum confluent flow problem, Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems, Graphic Submodular Function Minimization: A Graphic Approach and Applications, Single-Sink Multicommodity Flow with Side Constraints, Multi-item Vickrey-English-Dutch auctions, Pathwidth, trees, and random embeddings, Sets in excess demand in simple ascending auctions with unit-demand bidders, On the strength of connectedness of a random graph, Probabilistic strategy-proof rules over single-peaked domains, Quantitative Models for Infrastructure Restoration After Extreme Events: Network Optimization Meets Scheduling, Memory model sensitive bytecode verification, Minimum cuts and related problems, Balanced flows for transshipment problems, A Primal-Dual Algorithm for Weighted Abstract Cut Packing, Proving total dual integrality with cross-free families—A general framework, Maximum Flows and Minimum Cuts in the Plane, A primal simplex variant for the maximum-flow problem, Min-Max MPC based on a network problem, Abstract flows over time: a first step towards solving dynamic packing problems, IFORS' Operational Research Hall of Fame Delbert Ray Fulkerson, A branch-and-cut algorithm for scheduling of projects with variable-intensity activities, Segmentation of choroidal boundary in enhanced depth imaging octs using a multiresolution texture based modeling in graph cuts, A generalization of max flow—min cut, Meet and merge: approximation algorithms for confluent flows, AO(nm log(U/n)) time maximum flow algorithm, The partial inverse minimum cut problem withL₁-norm is strongly NP-hard, Lattices and Maximum Flow Algorithms in Planar Graphs, Minimum Cuts of Simple Graphs in Almost Always Linear Time, Modulus on graphs as a generalization of standard graph theoretic quantities, MINIMUM FLOW VARIATION IN MAXIMUM FLOWS, Unnamed Item, Engpässe, Staustellen und glatte homogene Ströme in Netzen, Asymptotic enumeration of orientations of a graph as a function of the out-degree sequence, The undirected two disjoint shortest paths problem, A survey of network interdiction models and algorithms, Theoretical and computational advances for network diversion, On optimal operation of communication nets, The Minimum Weight In-Tree Cover Problem, Faster graph bipartization, Equilibria and control of metabolic networks with enhancers and inhibitors, Single Commodity-Flow Algorithms for Lifts of Graphic and CoGraphic Matroids, Iterative Compression for Exactly Solving NP-Hard Minimization Problems, Traffic Networks and Flows over Time, Fractional matching preclusion number of graphs and the perfect matching polytope, On the optimum synthesis of statistical communication nets - pseudo parametric techniques, Optimization of communication nets with switching, Analysis and design of communication networks with memory, A generalized dynamic flows problem, Formalizing the Edmonds-Karp Algorithm, On r-regular r-connected non-hamiltonian graphs, Optimal Partial Tiling of Manhattan Polyominoes, The sensitivity of a traffic network, The effectiveness of finite improvement algorithms for finding global optima, Implementing Goldberg's max-flow-algorithm ? A computational investigation, Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms, Cycle Extensions in BIBD Block-Intersection Graphs, Conditional connectivity, Polynomial algorithms for (integral) maximum two-flows in vertex\(\backslash\)edge-capacitated planar graphs, Stability of metabolic networks via linear-in-flux-expressions, On the parameterized complexity of separating certain sources from the target, Maximum-throughput dynamic network flows, Capacity expansion and reliability evaluation on the networks flows with continuous stochastic functional capacity, I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs, A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs, Restricted Hausdorff content, Frostman's lemma and Choquet integrals, A fast parallel algorithm for minimum-cost small integral flows