A new approach to the maximum-flow problem
From MaRDI portal
Publication:3812009
DOI10.1145/48014.61051zbMath0661.90031OpenAlexW2090359754WikidataQ56018630 ScholiaQ56018630MaRDI QIDQ3812009
Andrew V. Goldberg, Robert Endre Tarjan
Publication date: 1988
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/48014.61051
Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)
Related Items
Stackelberg bipartite vertex cover and the preflow algorithm, Approximate decision algorithms for point set congruence, Computing maximum mean cuts, Improved balanced flow computation using parametric flow, Structural relatedness via flow networks in protein sequence space, Single-commodity robust network design with finite and hose demand sets, A fast preemptive scheduling algorithm with release times and inclusive processing set restrictions, On the time complexity of minimum and maximum global snapshot problems, A note on minimizing submodular functions, A distance constrained \(p\)-facility location problem on the real line, An analysis of the highest-level selection rule in the preflow-push max-flow algorithm, A fast cost scaling algorithm for submodular flow, A faster algorithm for computing the principal sequence of partitions of a graph, Efficient algorithms for the problems of enumerating cuts by non-decreasing weights, Production phase and ultimate pit limit design under commodity price uncertainty, Integer programming formulations for the elementary shortest path problem, Approximation schemes for bi-objective combinatorial optimization and their application to the TSP with profits, A branch-and-cut algorithm for the hub location and routing problem, Deadline-aware network coding for video on demand service over P2P networks, Design of survivable IP-over-optical networks, Topology optimisation of repairable flow networks for a maximum average availability, Optimal channel allocation for several types of cellular radio networks, On strongly polynomial dual simplex algorithms for the maximum flow problem, Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm, A branch-and-cut algorithm for the equicut problem, Strongly polynomial dual simplex methods for the maximum flow problem, Classes of submodular constraints expressible by graph cuts, Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time, Minimum cut problem using bases of extended polymatroids, Distributed strategies for generating weight-balanced and doubly stochastic digraphs, Hypergraphic submodular function minimization, Optimally solving the joint order batching and picker routing problem, Inefficiencies in network models: a graph-theoretic perspective, Global binary optimization on graphs for classification of high-dimensional data, A new approximation algorithm for the unbalanced min \(s\)-\(t\) cut problem, Weighted maximum-clique transversal sets of graphs, Simplifying maximum flow computations: the effect of shrinking and good initial flows, Domain decomposition methods with graph cuts algorithms for total variation minimization, The maximum flow problem of uncertain network, Aggregation of monotone reciprocal relations with application to group decision making, A push-relabel framework for submodular function minimization and applications to parametric optimization, Improving graph partitions using submodular functions., The reduction and fusion of fuzzy covering systems based on the evidence theory, Parametric stable marriage and minimum cuts, Generating pseudo-random permutations and maximum flow algorithms, Algorithms for distributing telecommunication traffic on a multiple-ring SONET-based network., On maximum flows in polyhedral domains, Graph clustering, An \(O(mn \log (nU))\) time algorithm to solve the feasibility problem, Formalizing network flow algorithms: a refinement approach in Isabelle/HOL, Polyhedral study of the connected subgraph problem, Use of dynamic trees in a network simplex algorithm for the maximum flow problem, A note on balanced flows in equality networks, Implementation of parallel branch-and-bound algorithms --- experiences with the graph partitioning problem, A testing based extraction algorithm for identifying significant communities in networks, The minimum vulnerability problem, Faster algorithms for security games on matroids, Finding minimum-cost flows by double scaling, On the computational behavior of a polynomial-time network flow algorithm, Exploiting planarity in separation routines for the symmetric traveling salesman problem, Dynamic evolution of economically preferred facilities, Two strongly polynomial cut cancelling algorithms for minimum cost network flow, New algorithms for the intersection problem of submodular systems, Bisection approach for pixel labelling problem, Efficient branch-and-bound algorithms for weighted MAX-2-SAT, An efficient algorithm for the evacuation problem in a certain class of networks with uniform path-lengths, 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 fast exact algorithm for the problem of optimum cooperation and the structure of its solutions, The axiomatization of override and update, Due dates assignment and JIT scheduling with equal-size jobs, Low-energy excitations in the three-dimensional random-field Ising model, A new strategy for the undirected two-commodity maximum flow problem, Structural and algorithmic properties for parametric minimum cuts, A new algorithm for solving the feasibility problem of a network flow, Maximizing network throughput under stochastic user equilibrium with elastic demand, Submodular function minimization, Executability of scenarios in Petri nets, An efficient minimum and maximum global snapshot algorithm, The universally quickest transshipment problem in a certain class of dynamic networks with uniform path-lengths, Extracting maximal information about sets of minimum cuts, An exact combinatorial algorithm for minimum graph bisection, Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\), A heuristic for blocking flow algorithms, Minimization of locally defined submodular functions by optimal soft arc consistency, Compression and denoising using \(l _{0}\)-norm, Computational investigations of maximum flow algorithms, Counting and sampling minimum \((s,t)\)-cuts in weighted planar graphs in polynomial time, Finding minimum 3-way cuts in hypergraphs, Diagnosing infeasibilities in network flow problems, Symmetric flows and broadcasting in hypercubes, Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations, A note on optimal covering augmentation for graphic polymatroids., A new saling algorithm for the maximum mean cut problem, A faster parametric minimum-cut algorithm, The maximum flow problem: A max-preflow approach, A fast algorithm for minimum weight odd circuits and cuts in planar graphs, On the complexity of preflow-push algorithms for maximum-flow problems, Non delayed relax-and-cut algorithms, Minimum Cuts in Surface Graphs, Efficient Implementation of a Synchronous Parallel Push-Relabel Algorithm, Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search, Recent developments in maximum flow algorithms, THE LAYERED NET SURFACE PROBLEMS IN DISCRETE GEOMETRY AND MEDICAL IMAGE SEGMENTATION, An improved direct labeling method for the max-flow min-cut computation in large hypergraphs and applications, Optimization Strategies for Resource-Constrained Project Scheduling Problems in Underground Mining, Unnamed Item, Parallelism, concurrency and distribution in constraint handling rules: A survey, EFFICIENT ALGORITHM FOR OPTIMAL MATRIX ORTHOGONAL DECOMPOSITION PROBLEM IN INTENSITY-MODULATED RADIATION THERAPY, Strength and reinforcement of a network and tree packing, Unnamed Item, Simple linear flow decomposition algorithms on trees, circles, and augmented trees, Simplifications and speedups of the pseudoflow algorithm, Minimum‐weight subgraphs with unicyclic components and a lower‐bounded girth, Exact and Approximation Algorithms for the Expanding Search Problem, TBGMax: leveraging two-boundary graph pattern for lossless maximum-flow acceleration, Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time, On implementing push-relabel method for the maximum flow problem, Generalized max flows and augmenting paths, Tight Localizations of Feedback Sets, $k$-Fibonacci numbers and $k$-Lucas numbers and associated bipartite graphs, A fast maximum flow algorithm, Lexicographically optimal earliest arrival flows, Heuristic approaches for the family traveling salesman problem, ReLU neural networks of polynomial size for exact maximum flow computation, In search of dense subgraphs: How good is greedy peeling?, Maximum skew-symmetric flows, Extracting densest sub-hypergraph with convex edge-weight functions, Mesh quality agglomeration algorithm for the virtual element method applied to discrete fracture networks, 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, Deciding Simulations on Probabilistic Automata, A vertex-separator-based integer linear programming formulation for the partitioned Steiner tree problem, Efficient Algorithms for the k Smallest Cuts Enumeration, Computing Maximum Flows in Undirected Planar Networks with Both Edge and Vertex Capacities, Unnamed Item, Unnamed Item, An integer L-shaped algorithm for the vehicle routing problem with time windows and stochastic demands, Unnamed Item, A theoretical and computational study of green vehicle routing problems, Popular critical matchings in the many-to-many setting, A new maximal flow algorithm for solving optimization problems with linguistic capacities and flows, Unnamed Item, Adjacency-Clustering and Its Application for Yield Prediction in Integrated Circuit Manufacturing, Densities, Matchings, and Fractional Edge-Colorings, A Distributed-Memory Algorithm for Computing a Heavy-Weight Perfect Matching on Bipartite Graphs, On the critical exponent α of the 5D random-field Ising model, Edge-Cuts of Optimal Average Weights, The Complexity of Valued CSPs, 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, Two-Dimensional Phase Unwrapping via Balanced Spanning Forests, Practical Minimum Cut Algorithms, An Exact Algorithm for the Steiner Forest Problem, ASSIGNMENT QUERY AND ITS IMPLEMENTATION IN MOVING OBJECT DATABASES, Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks, Fast augmentation algorithms for maximising the output flow in repairable flow networks after edge failures, Inverse Shortest Path Models Based on Fundamental Cycle Bases, Parallel algorithms for the maximum flow problem with minimum lot sizes, On project scheduling with irregular starting time costs, A branch-and-bound algorithm for multi-dimensional quadratic 0–1 knapsack problems, Cost minimization in wireless networks with a bounded and unbounded number of interfaces, Minimum Cuts of Simple Graphs in Almost Always Linear Time, Cost Minimisation in Multi-interface Networks, The basic train makeup problem in shunting yards, Computing Nash equilibria for scheduling on restricted parallel links, Unnamed Item, Evaluation of a Flow-Based Hypergraph Bipartitioning Algorithm, Close-to-optimal algorithm for rectangular decomposition of 3D shapes, EFFICIENT ALGORITHMS FOR THE OPTIMAL-RATIO REGION DETECTION PROBLEMS IN DISCRETE GEOMETRY WITH APPLICATIONS, The generalized minimum spanning tree problem: Polyhedral analysis and branch-and-cut algorithm, 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, Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs, A comprehensive simplex-like algorithm for network optimization and perturbation analysis, Parametric Shortest-Path Algorithms via Tropical Geometry, Analysis of Biological Data by Graph Theory Approach Searching of Iron in Biological Cells, Network Flow-Based Refinement for Multilevel Hypergraph Partitioning, An algorithm for improved delay-scaling in input-queued switches, Sequential and parallel algorithms for minimum flows., Survivability in hierarchical telecommunications networks, The assignment problem revisited, TRAWLING TRAFFIC UNDER ATTACK OVERCOMING DDoS ATTACKS BY TARGET-CONTROLLED TRAFFIC FILTERING, On swarm-level resource allocation in BitTorrent communities, Strength of a graph and packing of trees and branchings, Free multiflows in bidirected and skew-symmetric graphs, Separation, dimension, and facet algorithms for node flow polyhedra, Constructing the minimization diagram of a two-parameter problem, A branch-and-cut algorithm for the preemptive swapping problem, Separation of partition inequalities with terminals, Supermodular functions and the complexity of MAX CSP, On some large-scale LP relaxations for the graph partitioning problem and their optimal solutions, HNCcorr: combinatorial optimization for neuron identification, An efficient cost scaling algorithm for the assignment problem, On the complexity of nonnegative-matrix scaling, Strongly polynomial simplex algorithm for bipartite vertex packing, A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms, Enhanced instance space analysis for the maximum flow problem, Computing Behavioral Relations for Probabilistic Concurrent Systems, Co-density and fractional edge cover packing, Minimum-cost flow algorithms: an experimental evaluation, Simple push-relabel algorithms for matroids and submodular flows, Round-Optimal Perfectly Secret Message Transmission with Linear Communication Complexity, Minimizing energies with hierarchical costs, A golden ratio parameterized algorithm for cluster editing, The vertex \(k\)-cut problem, Packing chained items in aligned bins with applications to container transshipment and project scheduling, Just-in-Time Scheduling with Equal-Size Jobs, Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems, The symbolic algorithms for maximum flow in networks, Graphic Submodular Function Minimization: A Graphic Approach and Applications, Fair-by-design matching, Faster algorithms for stable allocation problems, Precedence constrained scheduling to minimize sum of weighted completion times on a single machine, Topologically trivial closed walks in directed surface graphs, Multigraph augmentation under biconnectivity and general edge-connectivity requirements, A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine, A spatially continuous max-flow and min-cut framework for binary labeling problems, Stronger MIP formulations for the Steiner forest problem, Partition-based logical reasoning for first-order and propositional theories, A primal-dual method for approximating tree cover with two weights, On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms, A new?old algorithm for minimum-cut and maximum-flow in closure graphs, Efficient preflow push algorithms, Crown reductions for the minimum weighted vertex cover problem, The separation problem of rounded capacity inequalities: some polynomial cases, The traveling purchaser problem and its variants, Distribution and reliability evaluation of MAX-flow in dynamic multi-state flow networks, Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches, Combined optimisation of an open-pit mine outline and the transition depth to underground mining, Shape matching and modeling using skeletal context, A note on the parametric maximum flow problem and some related reoptimization issues, Complexity and algorithms for nonlinear optimization problems, A distributed mincut/maxflow algorithm combining path augmentation and push-relabel, The distance constrained multiple vehicle traveling purchaser problem, A computational study of the capacity scaling algorithm for the maximum flow problem, A branch and cut algorithm for minimum spanning trees under conflict constraints, Universally maximum flow with piecewise-constant capacities, A two-phase greedy algorithm to locate and allocate hubs for fixed-wireless broadband access, Segmentation of choroidal boundary in enhanced depth imaging octs using a multiresolution texture based modeling in graph cuts, The Nemhauser-Trotter reduction and lifted message passing for the weighted CSP, Greedy splitting algorithms for approximating multiway partition problems, A new approach for computing a most positive cut using the minimum flow algorithms, Minimax inverse problems of minimum cuts, Exact solution algorithms for the maximum flow problem with additional conflict constraints, A branch-and-cut algorithm for the k-edge connected subgraph problem, Generalized \(k\)-multiway cut problems, Coupling feasibility pump and large neighborhood search to solve the Steiner team orienteering problem, Partitioning a graph into balanced connected classes: formulations, separation and experiments, Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs, Throughput analysis in wireless networks with multiple users and multiple channels, A neural network algorithm for semi-supervised node label learning from unbalanced data, Approximating the smallest 2-vertex connected spanning subgraph of a directed graph, Optimizing compatible sets in wireless networks through integer programming, Improved approximations for two-stage MIN-cut and shortest path problems under uncertainty, Computing minimum multiway cuts in hypergraphs, A hybrid artificial immune network for detecting communities in complex networks, 3D reconstruction with depth prior using graph-cut, Implementing an efficient minimum capacity cut algorithm, Resource-constrained project scheduling: Notation, classification, models, and methods, Capacitated multi-layer network design with unsplittable demands: polyhedra and branch-and-cut, Path planning for unmanned vehicles with localization constraints, Reconstruction, optimization, and design of heterogeneous materials and media: basic principles, computational algorithms, and applications, Network disconnection games: a game theoretic approach to checkpoint evaluation in networks, Formalizing the Edmonds-Karp Algorithm, Using the graph-cut method to segment the mineralization area in the gejiu region of Yunnan province, China, Distance metric learning for graph structured data, Modelling and Solving the Joint Order Batching and Picker Routing Problem in Inventories, Polyhedral structure of submodular and posi-modular systems, Finding a Maximum-Weight Convex Set in a Chordal Graph, On chromatic number and minimum cut, On some algorithmic aspects of hypergraphic matroids, Network reinforcement, Two-edge connected subgraphs with bounded rings: Polyhedral results and branch-and-cut, Maximum network flow with floating point arithmetic., A primal-dual approximation algorithm for the survivable network design problem in hypergraphs, Optimal flow and capacity allocation in multiple joint quickest paths of directed networks, Two deadline reduction algorithms for scheduling dependent tasks on parallel processors
