Analysis of Preflow Push Algorithms for Maximum Network Flow

DOI10.1137/0218072MaRDI QIDQ3034814zbMATH OpenOpenAlexFDO

Authors 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

distributed maximum flow algorithmheuristicsmaximum flow problemparametrized worst-case networkpreflow push algorithms

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4079142
• A new approach to the maximum-flow problem
• On the complexity of preflow-push algorithms for maximum-flow problems
• Some Recent Advances in Network Flows
• Computational investigations of maximum flow algorithms

Cited in

(26)

• 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
• Computational investigations of maximum flow algorithms
• Diagnosing infeasibilities in network flow problems
• A faster parametric minimum-cut algorithm
• On the complexity of preflow-push algorithms for maximum-flow problems
• An algorithmic study of the maximum flow problem: A comparative statistical analysis
• Scheduling jobs on identical machines with agreement graph
• A generalization of the scaling max-flow algorithm
• An auction algorithm for the max-flow problem
• Evacuation planning by earliest arrival contraflow
• Preemptive benchmarking problem: An approach for official statistics in small areas
• Efficient preflow push algorithms
• FIFO preflow algorithm for maximum flow in semi-bipartite networks
• 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
• Reducing complexities of the distributed max-flow and breadth-first-search algorithms by means of network synchronization
• scientific article; zbMATH DE number 4079142 (Why is no real title available?)
• scientific article; zbMATH DE number 176469 (Why is no real title available?)
• AO(nm log(U/n)) time maximum flow algorithm
• On implementing push-relabel method for the maximum flow problem
• The Bipartite Boolean Quadric Polytope with Multiple-Choice Constraints
• More efficient parallel flow algorithms
• The maximum flow problem: A max-preflow approach
• Complexity analysis for maximum flow problems with arc reversals

This page was built for publication: Analysis of Preflow Push Algorithms for Maximum Network Flow

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3034814)