On implementing the push-relabel method for the maximum flow problem
From MaRDI portal
Publication:1386767
DOI10.1007/PL00009180zbMath0898.68029DBLPjournals/algorithmica/CherkasskyG97OpenAlexW2152216760WikidataQ59700076 ScholiaQ59700076MaRDI QIDQ1386767
Andrew V. Goldberg, Boris V. Cherkassky
Publication date: 26 May 1998
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/pl00009180
Parallel algorithms in computer science (68W10) Specification and verification (program logics, model checking, etc.) (68Q60)
Related Items (66)
Optimal monotone relabelling of partially non-monotone ordinal data ⋮ Exact approaches to the single-source network loading problem ⋮ Structural relatedness via flow networks in protein sequence space ⋮ Single-commodity robust network design with finite and hose demand sets ⋮ A generalization of the scaling max-flow algorithm ⋮ An analysis of the highest-level selection rule in the preflow-push max-flow algorithm ⋮ Hop constrained Steiner trees with multiple root nodes ⋮ 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 ⋮ Solving a \(k\)-node minimum label spanning arborescence problem to compress fingerprint templates ⋮ Integer programming models and branch-and-cut approaches to generalized \(\{0,1,2\}\)-survivable network design problems ⋮ Approximation algorithms for treewidth ⋮ Optimization Strategies for Resource-Constrained Project Scheduling Problems in Underground Mining ⋮ Locating leak detecting sensors in a water distribution network by solving prize-collecting Steiner arborescence problems ⋮ Orientation-based models for \(\{0,1,2\}\)-survivable network design: theory and practice ⋮ The Generalized Regenerator Location Problem ⋮ Anomalous electrical and frictionless flow conductance in complex networks ⋮ Branch-and-cut methods for the network design problem with vulnerability constraints ⋮ Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem ⋮ ILP heuristics and a new exact method for bi-objective 0/1 ILPs: application to fttx-network design ⋮ Enhanced instance space analysis for the maximum flow problem ⋮ Simplifications and speedups of the pseudoflow algorithm ⋮ Minimum-cost flow algorithms: an experimental evaluation ⋮ PILOT, GRASP, and VNS approaches for the static balancing of bicycle sharing systems ⋮ Extended formulations and branch-and-cut algorithms for the black-and-white traveling salesman problem ⋮ A node-based layered graph approach for the Steiner tree problem with revenues, budget and hop-constraints ⋮ A survey on exact algorithms for the maximum flow and minimum‐cost flow problems ⋮ An exact algorithm for solving the vertex separator problem ⋮ Thinning out Steiner trees: a node-based model for uniform edge costs ⋮ Aggregation of monotone reciprocal relations with application to group decision making ⋮ Fair-by-design matching ⋮ On the critical exponent α of the 5D random-field Ising model ⋮ Formalizing network flow algorithms: a refinement approach in Isabelle/HOL ⋮ Mathematical Programming Algorithms for Spatial Cloaking ⋮ Rapidly Solving an Online Sequence of Maximum Flow Problems with Extensions to Computing Robust Minimum Cuts ⋮ Stronger MIP formulations for the Steiner forest problem ⋮ Branch-and-cut-and-price for capacitated connected facility location ⋮ Partition-based logical reasoning for first-order and propositional theories ⋮ Solving the minimum label spanning tree problem by mathematical programming techniques ⋮ A column generation approach for multicast routing and wavelength assignment with delay constraints in heterogeneous WDM networks ⋮ An Exact Algorithm for the Steiner Forest Problem ⋮ A new?old algorithm for minimum-cut and maximum-flow in closure graphs ⋮ Efficient preflow push algorithms ⋮ A distributed mincut/maxflow algorithm combining path augmentation and push-relabel ⋮ Efficient branch-and-bound algorithms for weighted MAX-2-SAT ⋮ Adaptive memory in multistart heuristics for multicommodity network design ⋮ A computational study of the capacity scaling algorithm for the maximum flow problem ⋮ Rapidly computing robust minimum capacity s-t cuts: a case study in solving a sequence of maximum flow problems ⋮ Models and methods for standardization problems ⋮ MIP models for connected facility location: a theoretical and computational study ⋮ Transport between multiple users in complex networks ⋮ Low-energy excitations in the three-dimensional random-field Ising model ⋮ Improved algorithms for the Steiner problem in networks ⋮ A visibility-based surface reconstruction method on the GPU ⋮ An efficient network flow code for finding all minimum cost \(s-t\) cutsets ⋮ A surface reconstruction method using global graph cut optimization ⋮ A compaction scheme and generator for distribution networks ⋮ Lagrangian decompositions for the two-level FTTx network design problem ⋮ Computational investigations of maximum flow algorithms ⋮ A tailored Benders decomposition approach for last-mile delivery with autonomous robots ⋮ Strong Formulations for 2-Node-Connected Steiner Network Problems ⋮ The two-level diameter constrained spanning tree problem ⋮ An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem ⋮ Exact approaches for solving robust prize-collecting Steiner tree problems ⋮ Dimensioning multicast-enabled communications networks
This page was built for publication: On implementing the push-relabel method for the maximum flow problem
