Analysis of Preflow Push Algorithms for Maximum Network Flow

DOI10.1137/0218072zbMath0692.68028OpenAlexW2029266474MaRDI QIDQ3034814

S. N. Maheshwari, Joseph Cheriyan

Publication date: 1989

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/4ced3d3dc43567dee365a48f6ee704d246ba57da

zbMATH Keywords

heuristicsmaximum flow problemdistributed maximum flow algorithmparametrized worst-case networkpreflow push algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)

Related Items

Evacuation planning by earliest arrival contraflow, A generalization of the scaling max-flow algorithm, An analysis of the highest-level selection rule in the preflow-push max-flow algorithm, Optimal relay node placement in delay constrained wireless sensor network design, Preemptive benchmarking problem: An approach for official statistics in small areas, An auction algorithm for the max-flow problem, On implementing push-relabel method for the maximum flow problem, The Bipartite Boolean Quadric Polytope with Multiple-Choice Constraints, Processor-efficient implementation of a maximum flow algorithm, Auction algorithms for network flow problems: A tutorial introduction, New algorithms for the intersection problem of submodular systems, Complexity analysis for maximum flow problems with arc reversals, Scheduling jobs on identical machines with agreement graph, AO(nm log(U/n)) time maximum flow algorithm, Computational investigations of maximum flow algorithms, Diagnosing infeasibilities in network flow problems, An algorithmic study of the maximum flow problem: A comparative statistical analysis, A faster parametric minimum-cut algorithm, The maximum flow problem: A max-preflow approach, On the complexity of preflow-push algorithms for maximum-flow problems